链式顺序表

一、链式存储逻辑结构

n个结点链接成一个链式线性表的结构叫做链表，
当每个结点中只包含一个指针域时，叫做单链表

①表头结点

链表中的第一个结点，包含指向第一个数据元素的指针以及

链表自身的一些信息
②数据结点
链表中代表数据元素的结点，包含指向下一个数据元素的指
针和数据元素的信息
③尾结点
链表中的最后一个数据结点，其下一元素指针为空，表示无
后继

二、插入元素到位置pos的算法

1.判断线性表是否合法
2.判断插入位置是否合法
3.由表头开始通过next指针移动pos次后，当前元素的next指
针即指向要插入的位置
4.将新元素插入
5.线性表长度加1

三、删除第pos个元素的算法
1.判断线性表是否合法
2.判断插入位置是否合法
3.获取第pos个元素
4.将第pos个元素从链表中删除
5.线性表长度减1

 1 #ifndef _LINKLIST_H_//linklist.h
 2 #define _LINKLIST_H_
 3 
 4 typedef void LinkList;
 5 typedef struct _tag_LinkListNode LinkListNode;
 6 struct _tag_LinkListNode
 7 {
 8     LinkListNode* next;
 9 };
10 
11 LinkList* LinkList_Create();
12 
13 void LinkList_Destroy(LinkList* list);
14 
15 void LinkList_Clear(LinkList* list);
16 
17 int LinkList_Length(LinkList* list);
18 
19 int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);
20 
21 LinkListNode* LinkList_Get(LinkList* list, int pos);
22 
23 LinkListNode* LinkList_Delete(LinkList* list, int pos);
24 
25 #endif

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #include "LinkList.h"
  4 
  5 typedef struct _tag_LinkList
  6 {
  7     LinkListNode header;
  8     int length;
  9 } TLinkList;
 10 
 11 LinkList* LinkList_Create() // O(1)
 12 {
 13     TLinkList* ret = (TLinkList*)malloc(sizeof(TLinkList));
 14     
 15     if( ret != NULL )
 16     {
 17         ret->length = 0;
 18         ret->header.next = NULL;
 19     }
 20     
 21     return ret;
 22 }
 23 
 24 void LinkList_Destroy(LinkList* list) // O(1)
 25 {
 26     free(list);    
 27 }
 28 
 29 void LinkList_Clear(LinkList* list) // O(1)
 30 {
 31     TLinkList* sList = (TLinkList*)list;
 32     
 33     if(
 34     sList != NULL )
 35     {
 36         sList->length = 0;
 37         sList->header.next = NULL;
 38     }
 39 }
 40 
 41 int LinkList_Length(LinkList* list) // O(1)
 42 {
 43     TLinkList* sList = (TLinkList*)list;
 44     int ret = -1;
 45     
 46     if( sList != NULL )
 47     {
 48         ret = sList->length;
 49     }
 50     
 51     return ret;
 52 }
 53 
 54 int LinkList_Insert(LinkList* list, LinkListNode* node, int pos) // O(n)
 55 { 
 56     TLinkList* sList = (TLinkList*)list;
 57     int ret = (sList != NULL) && (pos >= 0) && (node != NULL);
 58     int i = 0;
 59     
 60     if( ret )
 61     {
 62         LinkListNode* current = (LinkListNode*)sList;
 63         
 64         for(i=0; (i<pos) && (current->next != NULL); i++)
 65         {
 66             current = current->next;
 67         }
 68         
 69         node->next = current->next;
 70         current->next = node;
 71         
 72         sList->length++;
 73     }
 74     
 75     return ret;
 76 }
 77 
 78 LinkListNode* LinkList_Get(LinkList* list, int pos) // O(n)
 79 {
 80     TLinkList* sList = (TLinkList*)list;
 81     LinkListNode* ret = NULL;
 82     int i = 0;
 83     
 84     if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
 85     {
 86         LinkListNode* current = (LinkListNode*)sList;
 87         
 88         for(i=0; i<pos; i++)
 89         {
 90             current = current->next;
 91         }
 92         
 93         ret = current->next;
 94     }
 95     
 96     return ret;
 97 }
 98 
 99 LinkListNode* LinkList_Delete(LinkList* list, int pos) // O(n)
100 {
101     TLinkList* sList = (TLinkList*)list;
102     LinkListNode* ret = NULL;
103     int i = 0;
104     
105     if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
106     {
107         LinkListNode* current = (LinkListNode*)sList;
108         
109         for(i=0; i<pos; i++)
110         {
111             current = current->next;
112         }
113         
114         ret = current->next;
115         current->next = ret->next;
116         
117         sList->length--;
118     }
119     
120     return ret;
121 }

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include "LinkList.h"
 4 
 5 struct Value
 6 {
 7     LinkListNode header;
 8     int v;
 9 };
10 
11 int main(int argc, char *argv[]) 
12 {
13     int i = 0;
14     LinkList* list = LinkList_Create();
15     
16     struct Value v1;
17     struct Value v2;
18     struct Value v3;
19     struct Value v4;
20     struct Value v5;
21     
22     v1.v = 1;
23     v2.v = 2;
24     v3.v = 3;
25     v4.v = 4;
26     v5.v = 5;
27     
28     LinkList_Insert(list, (LinkListNode*)&v1, LinkList_Length(list));
29     LinkList_Insert(list, (LinkListNode*)&v2, LinkList_Length(list));
30     LinkList_Insert(list, (LinkListNode*)&v3, LinkList_Length(list));
31     LinkList_Insert(list, (LinkListNode*)&v4, LinkList_Length(list));
32     LinkList_Insert(list, (LinkListNode*)&v5, LinkList_Length(list));
33     
34     for(i=0; i<LinkList_Length(list); i++)
35     {
36         struct Value* pv = (struct Value*)LinkList_Get(list, i);
37         
38         printf("%d
", pv->v);
39     }
40     
41     while( LinkList_Length(list) > 0 )
42     {
43         struct Value* pv = (struct Value*)LinkList_Delete(list, 0);
44         
45         printf("%d
", pv->v);
46     }
47     
48     LinkList_Destroy(list);
49     
50     return 0;
51 }