线性表的顺序存储

http://www.coder4.com/archives/3036

1、线性表也可以用顺序表示实现，即用一组地址连续的存储单元依次存储线性表的数据元素。特点是ai和ai+1位于相邻的存储单元上，只要确定了存储线性表的起始位置，任意元素都可以随机存取。

2、LOC(ai) = LOC(a1)+(i-1)*l

3、通常用数组来描述数据结构中的顺序存储结构。

4、线性表的顺序存储不同于数组的地方是：数组的大小是静态不动的；而线性表类似于C++中的vector，如果存储空间不够，会自动的增加内部空间，而这一切，对外部用户是透明的。

5、顺序存储的随机访问效率很高O(1)，但插入是个大问题，除非i=n+1，否则必须移动i之后的所有元素。一般来说，倒着写for(从n~i)会简单一些(插入应从后往前拷贝)。

6、同理，删除第i个元素，需要将第i+1至第n个元素依次向前移动一个位置（删除可以从pos从前往后copy）。

7、对于线性表的顺序存储，插入和删除平均都要费n/2的操作。

8、线性表的顺序存储，基础操作如下（初始化、插入、删除等）：

#include <stdio.h>
#include <stdlib.h>

#define INIT_SIZE 100
#define INCR_SIZE 20

struct ArrayList
{
	int* data;
	int length; // current pos
	int size; // space size
};

void list_init(struct ArrayList* list)
{
	list->data = (int*)malloc(sizeof(int)*INIT_SIZE);
	list->size = INIT_SIZE;
	list->length = 0;
}

void list_free(struct ArrayList* list)
{
	if(list==NULL)
	{
		return ;
	}
	if(list->data)
	{
		free(list->data);
	}
	list->length = 0;
	list->size = 0;
}

void append_list(struct ArrayList* list, int elem)
{
	// Check if size is enough
	if(list->length>=list->size)
	{
		// Remalloc and auto copy
		list->data = realloc(list->data, sizeof(int)*(list->size+INCR_SIZE));
		if(!list->data)
		{
			return ;
		}
		else
		{
			list->size+=INCR_SIZE;
		}
	}
	// Append to the last of data
	list->data[list->length++] = elem;
}

void list_insert(struct ArrayList* list, int pos, int elem)
{
	int i = 0;
	if(!list)
	{
		return ;
	}
	// Check if position i is valid
	if(pos<0 || pos>=list->length)
	{
		return ;
	}
	// Check if size is enough
	if(list->length>=list->size)
	{
		// Remalloc and auto copy
		list->data = realloc(list->data, sizeof(int)*(list->size+INCR_SIZE));
		if(!list->data)
		{
			return ;
		}
		else
		{
			list->size+=INCR_SIZE;
		}
	}
	// Move elements
	for(i=list->length; i>pos; i--)
	{
		list->data[i] = list->data[i-1];
	}
	// Copy elem to right position
	list->data[i] = elem;
	list->length++;
}

void list_delete(struct ArrayList* list, int pos)
{
	int i = 0;
	if(!list)
	{
		return ;
	}
	if(pos<0 || pos>=list->length)
	{
		return ;
	}
	// Move elements
	for(i=pos;i<list->length-1;i++)
	{
		list->data[i] = list->data[i+1];
	}
	list->length--;
}

void list_print(struct ArrayList* list)
{
	int i = 0;
	if(list==NULL)
	{
		return ;
	}
	for(i=0; i<list->length; i++)
	{
		printf("%d ", list->data[i]);
	}
	printf("\n");
}

int main()
{
	struct ArrayList list;
	int i = 0;
	list_init(&list);
	// Append elems
	for(i=0; i<10; i++)
	{
		append_list(&list, i);
	}
	//list_insert(&list, 3, 888);
	list_delete(&list, 0);
	//printf("%d\n", list.size);
	list_print(&list);
	list_free(&list);
	return 0;
}

线性表的链式存储

http://www.coder4.com/archives/3027

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");
}