/* * LinkedList * linc * 2013.2.26 */ #include <stdio.h> #include <stdlib.h> #include <time.h> #define OK 1 #define ERROR -1 #define TURE 1 #define FALSE 0 struct Node { int data; struct Node *next; }; typedef struct Node *Head; typedef struct Node *LinkedList; //create the linked list,head insert void createList(LinkedList *list,int size,Head *head) { /* *head = (Head)malloc(sizeof(struct Node)); printf("head test0"); (*head)->data = size; printf("head test1"); //(*head)->next = (*list); printf("head test2"); */ LinkedList tmpList; srand(time(0)); *list = (LinkedList)malloc(sizeof(struct Node)); (*list)->next = NULL; for(int i = 0; i < size; i++) { tmpList = (LinkedList)malloc(sizeof(struct Node)); tmpList->data = rand()%100 + 1; tmpList->next = (*list)->next; (*list)->next = tmpList; printf("list->data %d is %d\n",i,tmpList->data); } //head node tmpList = (LinkedList)malloc(sizeof(struct Node)); tmpList->data = size; tmpList->next = (*list)->next; (*list)->next =tmpList; /* while((*list) != NULL) { printf("data is %d\n",(*list)->data); (*list)->next; } */ } //get element of list int getElement(LinkedList list,int index,int *element) { printf("getElement\n"); LinkedList tmpList = list->next; printf("getElement---test\n"); int size = tmpList->data;//the list size printf("the size is %d\n",size); if(index > size) { return ERROR; } int count = 0; while(tmpList && count < index+1)//+1 for head node { printf("data is %d\n",tmpList->data); tmpList = tmpList->next; ++count; } if(!tmpList) return ERROR; *element = tmpList->data; return OK; } //clear list int clearList(LinkedList *list) { //use 2 points free the list LinkedList tmpList1,tmpList2; tmpList1 = (*list)->next; while(tmpList1) { printf("free the data is %d\n",tmpList1->data); tmpList2 = tmpList1->next; free(tmpList1); tmpList1 = tmpList2; } (*list)->next = NULL; return OK; } //insert //after index int insert(LinkedList *list,int index,int element) { printf("insert index is %d,element is %d\n",index,element); LinkedList tmpList = (*list)->next; int size = tmpList->data; if(index > size) { printf("ERROR:the index > size.\n"); return ERROR; } int count = 0; while(tmpList && count < index+1) { tmpList = tmpList->next; ++count; } if(!tmpList) return ERROR; LinkedList node = (LinkedList)malloc(sizeof(struct Node)); node->data = element; node->next = tmpList->next; tmpList->next = node; return OK; } //delete int delete(LinkedList *list,int index) { printf("delete,index is %d\n",index); LinkedList tmpList = (*list)->next; int size = tmpList->data; if(index > size) { printf("ERROR:the index > size.\n"); return ERROR; } int count = 0; while(tmpList && count < index+1) { tmpList = tmpList->next; ++count; } if(!tmpList) return ERROR; LinkedList node = tmpList->next; tmpList->next = node->next; free(node); return OK; } int main() { LinkedList *list; Head *head; createList(list,10,head); int i = 1; getElement(*list,5,&i); insert(list,5,20); printf("getElement is %d\n",i); getElement(*list,5,&i); printf("getElement is %d\n",i); delete(list,5); clearList(list); return 0; }
链式存储结构的优点在于它在找到目标元素后,删除或者插入都十分方便,只需将指针挪动一次就好;缺点就是不能像顺序存储结构那样迅速的找到目标元素,只能笨笨的一个一个元素的遍历下去。