线性表的链式存储实现（带头结点）

 1 #ifndef LINKLIST_H_INCLUDE
 2 #define LINKLIST_H_INCLUDE
 3 
 4 #include <stdio.h>
 5 #include <stdlib.h>
 6 #include <stdbool.h>
 7 
 8 #define ERROR -1
 9 
10 typedef int ElementType;
11 
12 typedef struct LNode* PtrToNode;
13 struct LNode{
14     ElementType Data;
15     PtrToNode Next;
16 };
17 
18 typedef PtrToNode Position;        //这里的位置某个结点的结点指针
19 typedef PtrToNode List;
20 
21 
22 List MakeEmpty();
23 
24 
25 //链表长度
26 int Length(List L);
27 
28 //根据位序查找元素
29 ElementType FindKth(List L, int K);
30 
31 //根据元素查找相应的结点
32 Position Find(List L, ElementType X);
33 
34 //在指定位置之后插入元素
35 List Insert(List L, ElementType X, int i);
36 
37 bool Delete(List L, int i);
38 
39 void printList(List L);
40 
41 
42 
43 
44 #endif

  1 #include "LinkedList.h"
  2 
  3 List MakeEmpty()
  4 {
  5     List L = (List)malloc(sizeof(struct LNode));
  6     L->Next = NULL;
  7     L->Data = 0;
  8     return L;
  9 }
 10 
 11 int Length(List L)
 12 {
 13     int cnt = 0;
 14     List p = L->Next;        //当前p指向第一个结点
 15     while (p)
 16     {
 17         cnt++;
 18         p = p->Next;
 19 
 20     }
 21     return cnt;
 22 
 23 }
 24 
 25 ElementType FindKth(List L, int K)
 26 {
 27     Position p = L->Next;
 28     int cnt = 1;
 29     while (p && cnt < K)
 30     {
 31         p = p->Next;
 32         cnt++;
 33     }
 34     if ((cnt == K) && p)
 35         return p->Data;
 36     else
 37         return ERROR;
 38 }
 39 
 40 Position Find(List L, ElementType X)
 41 {
 42     Position p = L -> Next;
 43     while (p && p->Data != X)
 44         p = p->Next;
 45     if (p)
 46         return p;
 47     else
 48         return NULL;
 49 }
 50 
 51 List Insert(List L, ElementType X, int i)
 52 {
 53     Position tmp, pre;
 54     tmp = (Position)malloc(sizeof(struct LNode));
 55 
 56     int cnt = 0;
 57     pre = L;
 58     while (pre && cnt < i - 1)
 59     {
 60         pre = pre->Next;
 61         cnt++;
 62     }
 63     if (pre == NULL || cnt != i - 1)        //如果所招结点不再L中
 64     {
 65         printf("Insert position parameter error!\n");
 66         free(tmp);
 67         return L;
 68     }
 69     else
 70     {
 71         tmp->Data = X;
 72         tmp->Next = pre->Next;
 73         pre->Next = tmp;
 74         return L;
 75     }
 76 
 77 }
 78 
 79 bool Delete(List L, int i)
 80 {
 81     Position tmp, pre;
 82     int cnt = 0;
 83     pre = L;
 84 
 85 
 86     while (pre && cnt < i - 1)
 87     {
 88         pre = pre->Next;
 89         cnt++;
 90     }
 91     if (pre == NULL || cnt != i - 1 || pre->Next == NULL)        //i出错或链表为空
 92     {
 93         printf("Delete position parameter error!\n");
 94         return false;
 95     }
 96     else
 97     {
 98         tmp = pre->Next;
 99         pre->Next = tmp->Next;
100         free(tmp);
101         return true;
102     }
103 
104 
105 }
106 
107 void printList(List L)
108 {
109     Position p;
110     p = L -> Next;
111     while (p)
112     {
113         printf("%d ", p->Data);
114         p = p->Next;
115     }
116     printf("\n");
117     return;
118 }