数据结构重读 - 线性表的链式存储

Leave a reply

1、链式存储，可以简称链表。

2、链表的一个结点(node)由两部分组成：数据域和指针域。

3、整个链表的存取必须从头指针开始，链表最后一个结点的指针为空，因此它是非随机存取的数据结构。

4、链表中插入结点：假设原结点为p，新结点为s，则：

s->next = p->next;

p->next = s;

不是很难理解吧……

5、基本操作还是比较简单的，下面假定采用无“空头”模式的如下链表：

#define INVALID 0xfffffff

struct Node
{
	int data;
	struct Node* next;
};

void make_list(struct Node* head, int* arr, int n)
{
	int i = 0;
	struct Node* ptr = NULL;
	if(n<=0)
	{
		return ;
	}
	// First node
	head->data = arr[0];
	head->next = NULL;
	ptr = head;

	for(i=1; i<n; i++)
	{
		ptr->next = (void*)malloc(sizeof(struct Node));
		ptr = ptr->next;
		if(!ptr)
		{
			return ;
		}
		ptr->data = arr[i];
	}
	ptr->next = NULL;
}

void free_list(struct Node* head)
{
	struct Node* ptr = head->next;
	struct Node* ptr_next = NULL;
	while(ptr!=NULL)
	{
		ptr_next = ptr->next;
		free(ptr);
		ptr = ptr_next;
	}
	head->data = 0;
	head->next = NULL;
}

void print_list(struct Node* head)
{
	struct Node* ptr = head;
	while(ptr!=NULL)
	{
                if(ptr->data!=INVALID)
                {
		    printf("%d ", ptr->data);
                    ptr = ptr->next;
                }
	}
	printf("\n");
}

6、假设链表A、B分别代表两个集合，现在要求A和B的并集操作。

基本思路：由于无法确定A、B都是有序的。检查B中每一个元素，如果在A中没有出现过，则插入到A中（注意集合的操作，必须考虑去重）。

void merge_list(struct Node* a, struct Node* b)
{
	struct Node *pa, *pb;
	pa = a;
	pb = b;
	// Check each node in b, if not found in a, add to a
	while(pb!=NULL)
	{
		pa = a;
		while(pa!=NULL)
		{
			if(pa->data == pb->data)
			{
				// Already in a, no need to insert
				break;
			}
			pa = pa->next;
		}
		if(pa==NULL)
		{
			// pb can't found in a, insert
			pa = a->next;
			a->next = (void*)malloc(sizeof(struct Node));
			a->next->data = pb->data;
			a->next->next = pa;
		}
		pb = pb->next;
	}
}

测试驱动如下：

int main()
{
    struct Node head1, head2;
    int arr1[5] = {1, 3, 5, 7, 9};
    int arr2[5] = {8, 5, 4, 3, 2};
    // Make list
    make_list(&head1, &arr1[0], 5);
    make_list(&head2, &arr2[0], 5);
    // Print list
    print_list(&head1);
    print_list(&head2);
    // Merge list
    merge_list(&head1, &head2);
    print_list(&head1);
    // Free list
    free_list(&head1);
    free_list(&head2);
    return 0;
}

输入：A = {1, 3, 5, 7, 9}  B = {8, 5, 4, 3, 2}
输出：A={1,2, 4, 8, 3, 5, 7, 9}

7、还是A、B是集合，但都有序（如都递增），求A和B的并集操作。

基本思路：类似归并。

需要注意的细节是，由于采用无头结构，会多分配一个（预分配结点），需要在最后释放掉。

void merge_list2(struct Node* pa, struct Node* pb, struct Node* pc)
{
	struct Node* pc_old = NULL;
	pc->next = NULL;
	pc->data = INVALID;
	while(pa!=NULL && pb!=NULL)
	{
		if(pa->data < pb->data)
		{
			pc->data = pa->data;
			pc->next = (void*)malloc(sizeof(struct Node));
			pc_old = pc;
			pc = pc->next;
			pa = pa->next;
		} else if(pa->data > pb->data)
		{
			pc->data = pb->data;
			pc->next = (void*)malloc(sizeof(struct Node));
			pc_old = pc;
			pc = pc->next;
			pb = pb->next;
		} else
		{
			pc->data = pb->data;
			pc->next = (void*)malloc(sizeof(struct Node));
			pc_old = pc;
			pc = pc->next;
			pa = pa->next;
			pb = pb->next;
		}
	}
	while(pa!=NULL)
	{
		pc->data = pa->data;
		pc->next = (void*)malloc(sizeof(struct Node));
		pc_old = pc;
		pc = pc->next;
		pa = pa->next;
	}
	while(pb!=NULL)
	{
		pc->data = pb->data;
		pc->next = (void*)malloc(sizeof(struct Node));
		pc_old = pc;
		pc = pc->next;
		pb = pb->next;
	}
	if(pc_old)
	{
		free(pc_old->next);
		pc_old->next = NULL;
	}
}

测试驱动：

输入： A = {1, 3, 5, 7, 9}  B = {1, 5, 9, 20, 27}
输出： C={1, 3, 5, 7, 9, 20, 27}

8、还是A、B是集合，还是都有序（如都递增），求A和B集合的交操作。

其实比并简单些：

void intersection_list2(struct Node* pa, struct Node* pb, struct Node* pc)
{
    struct Node* pc_old = NULL;
    pc->data = INVALID;
    pc->next = NULL;
    while(pa!=NULL && pb!=NULL)
    {
        if(pa->data==pb->data)
        {
            pc->data = pb->data;
            pc->next = (void*)malloc(sizeof(struct Node));
            pc_old = pc;
            pc = pc->next;
            pa = pa->next;
            pb = pb->next;
            continue;
        }
        else if(pa->data < pb->data)
        {
            pa = pa->next;
        }
        else//(pa->data > pb->data)
        {
            pb = pb->next;
        }
    }
    if(pc_old)
    {
        free(pc_old->next);
        pc_old->next = NULL;
    }
}

8、也可以用数组来描述线性链表，土名静态链表。

typedef struct
{
    int data;
    int next;
}Node, StaticList[MAXSIZE];

在如上的数据结构中，data还是存储数据，而指针next被替换成了数组下标next。

由于空间是以数组的形式预分配的，不再有NULL来判断一个结点是否有效。

我们要牺牲首尾元素[0]和[MAXSIZE-1]来构成两条链：
(1)[MAXSIZE-1]开始的链，为有效链，包含的data是有效的，通过next依次接下去。
(2)从[0]开始的链，为未分配链，当发生delete的时候，需要把无效的结点挂在这条链上。

还是由于空间都是以结点的形式预分配的，malloc、free的参数、返回值都将是下标而不再是指针，这些也都需要我们自己实现了。

注意：free和malloc都是针对free链即[0]有关的操作。

liheyuan@liheyuan-desktop:tmp$ cat ./staticlist.c
#include <stdio.h>

#define MAXSIZE 100

typedef struct
{
	int data;
	int next;
}Node, StaticList[MAXSIZE];
// StaticList 's [0] and [MAXSIZE-1] is reserve, not for data storage
// StaticList[0] is free node list
// StaticList[MAXSIZE-1] is active node list

void sl_init(StaticList list)
{
	// chunk the unused node(max-1 should reserve for data link)
	int i = 0;
	for(i=0;i<MAXSIZE-2;i++)
	{
		list[i].next = i+1;
	}
	// max-1 is active link, next==0 means end
	list[MAXSIZE-1].next = list[MAXSIZE-2].next = 0;
}

int sl_malloc(StaticList list)
{
	int i = list[0].next;
	if(i==0)
	{
		return -1;
	}
	else
	{
		list[0].next = list[i].next;
		return i;
	}
}

void sl_free(StaticList list, int j)
{
	list[i].next = list[0].next;
	list[0].next = j;
}

int main()
{
	int i;
	StaticList list;
	sl_init(list);
	while((i = sl_malloc(list))!=-1)
	{
		printf("%d ", i);
	}
	return 0;
}

9、静态链表的插入、删除操作。

首先是简单的push_back和push_front：

//push_back
void sl_push_back(StaticList list, int val)
{
    // Find the last elem in array
    int i = MAXSIZE-1;
    int new_pos = 0;
    while(list[i].next!=0)
    {   
        i = list[i].next;
    }   
    // Append the elem
    new_pos = sl_malloc(list);
    list[i].next = new_pos;
    list[new_pos].data = val;
    list[new_pos].next = 0;
}

//push_front
void sl_push_front(StaticList list, int val)
{
    // Append to the list head
    int new_pos = sl_malloc(list);
    list[new_pos].data = val;
    list[new_pos].next = list[MAXSIZE-1].next;
    list[MAXSIZE-1].next = new_pos;
}

然后是在指定位置删除和插入。

 

void sl_insert(StaticList list, int pos, int val)
{
    // Find the right pos   
    int j = MAXSIZE - 1;
    int i;
    int new_pos;
    if(pos<0)
    {
        return ;
    }
    for(i=0; i<pos && j!=0; i++)
    {
        j = list[j].next;
    } 
    if(i!=pos)
    {
        return ;
    }
    // Insert
    new_pos = sl_malloc(list);
    if(new_pos==-1)
    {
        return ;
    }
    list[new_pos].next = list[j].next;
    list[new_pos].data = val;
    list[j].next = new_pos;
}

void sl_delete(StaticList list, int pos)
{
    // Find the pos-1
    int j = MAXSIZE - 1;
    int i;
    int free_pos;
    if(pos<0)
    {  
        return ;
    }
    for(i=0; i<pos-1 && j!=0; i++)
    {  
        j = list[j].next;
    }
    if(i!=pos-1)
    {
        return ;
    }
    // Delete
    free_pos = list[j].next;
    list[j].next = list[free_pos].next;
    sl_free(list, free_pos);
}

10、

 

 

您可能也喜欢如下文章:

  1. 删除重复的链表 c语言实现
  2. 链表的就地反转 c语言实现
  3. 单链表的创建、插入、删除、查找
  4. 树的孩子-兄弟结点存储之Java实现
  5. 猴子选大王（约瑟夫环问题）c语言描述

Leave a Reply

Your email address will not be published. Required fields are marked *