线性表的特点

线性结构的特定是：在数据的非空有限集中

  1. 存在唯一的一个被称做第一个的数据元素
  2. 存在唯一的一个被称为最后一个的数据元素
  3. 除了第一个外，集合中所有数据元素都由一个前驱
  4. 除了最后一个外，集合中所有的元素都有一个后继

线性表的顺序表示和实现

  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. #define TRUE 1
  5. #define FALSE 0
  6. #define OK 1
  7. #define ERROR 0
  8. #define INFEASIBLE -1 // 英文翻译，不可行，不可能
  9. #define OVERFLOW -2 // 英文翻译，溢出
  11. typedef int Status;
  12. typedef int ElemType;
  13. // #define ElemType int
  15. #define LIST_INIT_SIZE 5 // 线性表初始分配量
  16. #define LISTINCREMENT 10 // 增量
  19. typedef struct {
  20.     ElemType * elem; // 线性表基地址
  21.   int length; // 列表长度
  22.   int listsize; // 当前分配存储容量（以sizeof(ElemType）为单位）
  23. } SqList;
  25. Status InitList_Sq(SqList *L) { // 创建一个线性表
  26.     (*L).elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
  27.   if (!(*L).elem) { // 存储分配失败
  28.     printf("创建失败\n");
  29.     exit(OVERFLOW);
  30.   }
  31.   (*L).length = 0; // 初始长度
  32.   (*L).listsize = LIST_INIT_SIZE; // 初始存储容量
  33.   printf("创建成功\n");
  34.   return OK;
  35. }
  37. Status ListInsert_Sq(SqList *L, int i, ElemType e) {
  38.     if (i < 1 || i > (*L).length + 1) {
  39.     printf("插入失败\n");
  40.     return ERROR;
  41.   }
  42.   if ((*L).length >= (*L).listsize) { // 存储空间已满，分配新内存
  43.     ElemType * newbase = (ElemType *)realloc((*L).elem, ((*L).listsize + LISTINCREMENT) * sizeof(ElemType));
  44.     if (!newbase) {
  45.       exit(OVERFLOW);
  46.     }
  47.     (*L).elem = newbase;
  48.     (*L).listsize += LISTINCREMENT;
  49.   }
  50.   ElemType *q = &((*L).elem[i - 1]);
  51.   printf("%p\n", q);
  52.   for (ElemType *p = &((*L).elem[(*L).length - 1]); p >= q; p--) {
  53.     // 插入位置及之后的元素右移
  54.     *(p+1) = *p;
  55.   }
  56.   *q = e;
  57.   ++(*L).length;
  58.   printf("插入成功\n");
  59.   return OK;
  60. }
  62. Status ListDelete_Sq(SqList *L, int i, ElemType *e) {
  63.   // 假设原有2位[1,3] i = 1;
  64.   // *p 指向第一个元素
  65.   // 通过指针给e赋值，相当于将被删除的元素值返回
  66.   // *q 指向最后一个元素
  67.   // 首先++p，现在p指向最后一个元素
  68.   // p <= q，p和q相等，将值左移一位
  69.   // p++ 后，指针出界，p > q, 不满足条件
  70.   if (i < 1 || i > (*L).length + 1) {
  71.     printf("删除失败\n");
  72.     return ERROR;
  73.   }
  74.   ElemType *p = &((*L).elem[i - 1]);
  75.   *e = *p;
  76.   ElemType *q = (*L).elem + (*L).length; // 指向最后一个元素 相当于 [] + length
  77.   for (++p; p <= q; ++p) {
  78.     *(p - 1) = *p;
  79.   }
  80.   --(*L).length;
  81.   printf("删除成功\n");
  82.   return OK;
  83. }
  85. int LocateElem_Sq(SqList *L, ElemType e, Status (* compare)(ElemType, ElemType)) {
  86.   int i = 1;
  87.   ElemType *p = (*L).elem;
  88.   while(i <= (*L).length && !(* compare)(*p++, e)) {
  89.     ++i;
  90.   }
  91.   if (i <= (*L).length) {
  92.     return i;
  93.   }
  94.   return 0;
  95. }
  97. Status compare(ElemType x, ElemType y) {
  98.   printf("%d,%d\n", x, y);
  99.   return x == y ? TRUE : FALSE;
  100. }
  102. Status DestroyList(SqList *L) { 
  103.   free((*L).elem);
  104.   (*L).elem = NULL;
  105.   printf("线性表被释放！表长度：%d\n", L->length);
  106.   printf("线性表被释放！表空间：%lu字节\n", L->listsize * sizeof(ElemType));
  107.   L->length = 0;
  108.   L->listsize = 0;
  109.   return OK;
  110. }
  112. int ListLength(SqList *L) {
  113.   return (*L).length;
  114. }
  116. Status ListEmpty(SqList *L) {
  117.   if ((*L).elem == NULL) {
  118.     return TRUE;
  119.   } 
  120.   return FALSE;
  121. }
  124. Status ClearList(SqList *L) {
  125.   if ((*L).elem != NULL) {
  126.     free((*L).elem);
  127.     (*L).elem = NULL;
  128.   }
  129.   (*L).elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
  130.   if (!(*L).elem) { // 存储分配失败
  131.     printf("重置为空表\n");
  132.     exit(OVERFLOW);
  133.   }
  134.   L->length = 0;
  135.   L->listsize = LIST_INIT_SIZE;
  136.   return OK;
  137. }
  142. int main(){
  143.   Status InitList_Sq(SqList *L);
  144.   Status ListInsert_Sq(SqList *L, int i, ElemType e);
  145.   Status ListDelete_Sq(SqList *L, int i, ElemType *e);
  146.   Status compare(ElemType x, ElemType y);
  147.   int LocateElem_Sq(SqList *L, ElemType e, Status (* compare)(ElemType, ElemType));
  148.   Status DestroyList(SqList *L);
  150.   SqList *list;
  151.   // 创建线性表
  152.   InitList_Sq(list);
  153.   printf("length=%d\n", (*list).length);
  154.   // 数据插入线性表
  155.   ListInsert_Sq(list, (*list).length + 1, 1990);
  156.   ListInsert_Sq(list, (*list).length + 1, 1991);
  157.   ListInsert_Sq(list, (*list).length + 1, 1991);
  158.   ListInsert_Sq(list, (*list).length + 1, 1991);
  159.   ListInsert_Sq(list, (*list).length + 1, 1991);
  160.   ListInsert_Sq(list, (*list).length + 1, 1991);
  161.   ListInsert_Sq(list, (*list).length + 1, 1991);
  162.   ListInsert_Sq(list, (*list).length + 1, 1991);
  163.   printf("length=%d\n", (*list).length);
  164.   // 删除线性表的数据
  165.   ElemType e;
  166.   ListDelete_Sq(list, 2, &e);
  167.   // printf("e=%d\n", e);
  168.   printf("listsize=%d\n", (*list).listsize);
  169.   e = 1991;
  170.   int index = LocateElem_Sq(list, e, *compare);
  171.   printf("index=%d\n", index);
  172.   DestroyList(list);
  173.   printf("ListEmpty=%d\n", ListEmpty(list));
  174.   printf("ClearList=%d\n", ClearList(list));
  175.   return 0;
  176. }

线性链表的实现

指针型

  1. #include <stdlib.h>
  2. #include <stdio.h>
  4. typedef int Status;
  5. typedef int ElemType;
  6. typedef struct LNode {
  7.   ElemType data;
  8.   int length;
  9.   struct LNode *next;
  10. }LNode, *LinkList;
  12. #define TRUE 1
  13. #define FALSE 0
  14. #define OK 1
  15. #define ERROR 0
  16. #define INFEASIBLE -1 // 英文翻译，不可行，不可能
  17. #define OVERFLOW -2 // 英文翻译，溢出
  19. Status CreateList_L(LinkList *L, int n) {
  20.   (*L) = (LinkList)malloc(sizeof(LNode));
  21.   (*L) -> next = NULL;
  22.   (*L) -> length = 0;
  23.   int i;
  24.   LinkList q;
  25.   for (i = n; i > 0; --i) {
  26.       LinkList p = (LinkList)malloc(sizeof(LNode));
  27.     printf("请输入数据:");
  28.     scanf("%d", &p -> data);
  29.     if ((*L) -> next == NULL) {
  30.       p -> next = (*L) -> next;
  31.       (*L) -> next = p;
  32.       q = p;
  33.       (*L) -> length += 1;
  34.     } else {
  35.       q -> next = p;
  36.       p -> next = NULL;
  37.       q = p;
  38.       (*L) -> length += 1;
  39.     }
  40.   }
  41.   return OK;
  42. }
  44. ElemType *GetElem_L(LinkList L, int i) {
  45.   LinkList p = L -> next;
  46.   int j = 1;
  47.   while(p && j < i) {
  48.     p = p -> next;
  49.     ++j;
  50.   }
  51.   if (!p || j > i) {
  52.     return ERROR;
  53.   }
  54.   return &(p -> data);
  55. }
  57. void printAll(LinkList L) {
  58.   LinkList p = L -> next;
  59.   int i = 1;
  60.   while(p != NULL) {
  61.     printf("item[%d]=%d\n",i, p -> data);
  62.     i++;
  63.     p = p -> next;
  64.   }
  65. }
  67. Status ListInsert_L(LinkList L, int i, ElemType e) {
  68.   LinkList p = L -> next;
  69.   int j = 0;
  70.   while (p && j < i - 1) {
  71.     p = p -> next;
  72.     ++j;
  73.   }
  74.   if (!p || j > i - 1) {
  75.     return ERROR;
  76.   }
  77.   LinkList s = (LinkList)malloc(sizeof(LNode));
  78.   s -> data = e;
  79.   s -> next = p -> next;
  80.   p -> next = s;
  81.   L -> length += 1;
  82.   return OK; 
  83. }
  85. Status ListDelete_L(LinkList L, int i, ElemType *e) {
  86.   LinkList p = L -> next;
  87.   int j = 1;
  88.   while (p && j < i - 1) {
  89.     p = p -> next;
  90.     ++j;
  91.   }
  92.   if (!(p -> next) || j > i - 1) {
  93.     return ERROR;
  94.   }
  95.   LinkList q = p -> next; // p = 要被删除的那个的前一个
  96.   p -> next = q -> next; 
  97.   *e = q -> data;
  98.   L -> length -= 1;
  99.   free(q);
  100.   return OK;
  101. }
  103. int main(){
  104.   Status CreateList_L(LinkList *L, int n);
  105.   ElemType *GetElem_L(LinkList L, int i);
  106.   LinkList list;
  107.   CreateList_L(&list, 2);
  108.   printf("item=%d\n", *GetElem_L(list, 1));
  109.   printf("item=%d\n", *GetElem_L(list, 2));
  110.   printf("length=%d\n", (*list).length);
  111.   ListInsert_L(list, (*list).length, 18);
  112.   printAll(list);
  113.   ElemType e;
  114.   printf("length=%d\n", (*list).length);
  115.   ListDelete_L(list, (*list).length, &e);
  116.   printf("e=%d\n", e);
  117.   printAll(list);
  118.   return 0;
  119. }

静态链表（用数组来表示的）

以i代替动态指针p，类似与 p = p -> next

  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. #define MAXSIZE 10
  6. typedef int ElemType;
  7. #define format_elem "%d"
  9. typedef struct {
  10.   ElemType data;
  11.   int cur; // 存储下标
  12. } component, SLinkList[MAXSIZE];
  14. void InitSpace_SL(SLinkList *S) { // 初始化
  15.   int i = 0;
  16.   for (i = 0; i < MAXSIZE - 1; ++i) {
  17.     S[i] -> cur = i + 1;
  18.   }
  19.   S[MAXSIZE - 1]-> cur = 0;
  20. }
  22. int Malloc_SL(SLinkList *S) { // 分配空间
  23.   int i = S[0]-> cur;
  24.   if (S[0]-> cur) {
  25.     S[0]-> cur = S[i]-> cur;
  26.   }
  27.   return i;
  28. }
  30. void Free_SL(SLinkList *S, int k) { // 释放空间
  31. }
  33. void printAll(SLinkList *S, int r) {
  34.   S[0]-> cur = S[r] -> cur;
  35.     while(S[0] -> cur != 0) {
  36.       printf("item[%d]=%d\n", r, S[r] -> data);
  37.     r = S[r] -> cur; // 指针下移
  38.     S[0] -> cur = r; // 指针下移
  39.   }
  40. }
  42. int main() {
  43.     SLinkList list;
  44.   InitSpace_SL(&list); // 初始化
  45.   int i = Malloc_SL(&list); // 获取头指针位置 i = 1
  46.   int r = i; // r 是头指针
  47.   (&list)[i] -> data = 11; // (&list)[i] -> cur = 2
  48.   i = Malloc_SL(&list); // 指针后移 i = 2
  49.   (&list)[i] -> data = 22; // (&list)[i] -> cur = 3
  50.   (&list)[i] -> cur = 0; // (&list)[i] -> cur = 0
  51.   printAll(&list, r);
  52. }

循环链表

循环链表和指针型链表表现一致，只是最后一个节点不的next不指向NULL，而是指向头指针

双向链表

  1. typedef struct DcLNode {
  2.     ElemType data;
  3.     struct DuLNode *prior; // 指向上一个节点
  4.     struct DuLNode *next; // 指向下一个节点
  5. }
  7. d = d -> next -> prior = d -> prior - next;