2.1. 线性表

2.1.1. 什么是线性表

线性表是由同类型的数据元素够坦诚有序序列的线性结构。

# 抽象结构描述

类型名称: List
数据对象集: 线性表是n个元素构成的有序序列(a1,a2,....an)
操作集:
    List MakeEmpty(): 初始化一个空线性表。
    ElementType FindKth(int K ,List L): 根据位序返回对应元素。
    int Find(ElementType X,List L): 查找X第一次出现的位序号。
    void Insert(ElementType X,int i,List L): 在位序前插入一个元素。
    void Delete(int i ,List L): 删除指定位序的元素。
    int Length(List L): 返回线性表L的长度n。

2.1.2. 线性表连续具体实现

 1#include <stdio.h>
 2#include <stdlib.h>
 3
 4#define MAXSIZE 5
 5#define ElementType int
 6
 7typedef struct LNode *List;
 8struct LNode {
 9    ElementType Data[MAXSIZE];
10    int Len;
11};
12
13List MakeEmpty() {
14    List ptrl;
15    ptrl = (List) malloc(sizeof(struct LNode));
16    ptrl->Len = 0;
17    return ptrl;
18}
19
20
21int Find(ElementType x, List ptrl) {
22    int i = 0;
23    while (i < ptrl->Len   && ptrl->Data[i] != x) {
24        i++;
25    }
26    if (i >= ptrl->Len   ) {
27        return -1;
28    }
29    return i;
30}
31
32void Insert( ElementType x, int i, List ptrl ) {
33
34    if (ptrl->Len >=MAXSIZE){
35        printf("表满了,不能再插入了。\n") ;
36        return  ;
37    }
38    if (i <0 || i >ptrl->Len){
39        printf("位置不合法\n");
40        return ;
41    }
42    int j =0 ;
43    for (j=ptrl->Len-1; j>=i ;j--){
44        ptrl->Data[j+1] = ptrl->Data[j] ;
45    }
46    ptrl->Data[i] = x ;
47    ptrl->Len +=1;
48}
49void Delete(int i , List ptrl){
50    if (i >=ptrl->Len || i<0) {
51        printf("删除位置不合适\n");
52        return;
53    }
54
55    int j=0;
56    for (j=i; j<ptrl->Len-1 ;j++){
57        ptrl->Data[j] = ptrl->Data[j+1];
58    }
59    ptrl->Len -=1;
60    return ;
61}
62
63
64void Print(List ptrl) {
65    int i;
66    for (i = 0; i < ptrl->Len; i++) {
67        printf("%d ", ptrl->Data[i]);
68    }
69    printf("\n");
70}
71
72
73int main() {
74    List ptrl;
75    int index ;
76
77    ptrl = MakeEmpty();
78    Insert(1,0,ptrl);
79    Insert(2,1,ptrl);
80    Insert(3,2,ptrl);
81    Insert(4,3,ptrl);
82    //Insert(5,4,ptrl);
83    // Insert(6,5,ptrl);
84    //Insert(6,7,ptrl);
85
86    index = Find(3,ptrl);
87    printf("find %d in list index=%d\n ",3, index);
88    Print(ptrl);
89
90    Delete(5,ptrl);
91    Print(ptrl);
92    Delete(0,ptrl);
93    Print(ptrl);
94
95    return 0;
96}
97

2.1.3. 线性表链式具体实现

  1#include <stdio.h>
  2#include <stdlib.h>
  3
  4#define ElementType int
  5
  6typedef struct LNode *List;
  7struct LNode
  8{
  9    ElementType Data;
 10    List Next;
 11};
 12
 13List MakeEmpty() {
 14    List ptrl = NULL;
 15    return ptrl;
 16}
 17
 18int Length(List ptrl){
 19    List p = ptrl ;
 20    int cnt =0 ;
 21    while  (p){
 22        p=p->Next;
 23        cnt +=1;
 24    }
 25    return cnt ;
 26}
 27List FindKth(int i , List ptrl){
 28    if (i<0){
 29        printf("位置不合适、n");
 30        return NULL ;
 31    }
 32    List p = ptrl   ;
 33    int j = 0;
 34    while (j<i && p!=NULL  ){
 35        j+=1;
 36        p=p->Next   ;
 37    }
 38    if ( j ==i ) {
 39        return p ;
 40    }
 41    return NULL;
 42}
 43
 44List Find(ElementType x, List ptrl) {
 45    List p = ptrl ;
 46    while (p!=NULL && p->Data !=x){
 47        p= p->Next;
 48    }
 49    return p  ;
 50}
 51
 52List Insert( ElementType x, int i, List ptrl ) {
 53    if (i == 0 ){
 54        List h = (List) malloc(sizeof(struct LNode));
 55        h->Data = x ;
 56        h->Next = ptrl ;
 57        return h ;
 58    }
 59
 60    List p = FindKth(i-1,ptrl) ;
 61    if (p == NULL){
 62        printf("参数i错误\n");
 63        return NULL;
 64    }
 65
 66    List s = (List) malloc(sizeof(struct LNode));
 67    s->Data =x ;
 68    s->Next = p->Next;
 69    p->Next = s ;
 70    return ptrl;
 71
 72}
 73List  Delete(int i , List ptrl){
 74    if (i == 0 ){
 75        List s = ptrl ;
 76        if (!ptrl) {
 77            free(s);
 78            return NULL;
 79        }
 80        ptrl = ptrl->Next    ;
 81        free(s);
 82        return ptrl ;
 83    }
 84
 85    List p = FindKth(i-1,ptrl) ;
 86    if (p == NULL){
 87        printf("参数i错误\n");
 88        return NULL;
 89    }
 90
 91    List s = p->Next ;
 92    p->Next = s->Next ;
 93    free(s);
 94    return ptrl;
 95}
 96
 97
 98void Print(List ptrl) {
 99   List  p= ptrl ;
100   if (p == NULL){
101       printf("p == NULL\n");
102       return ;
103   }
104   while (p){
105        printf("%d ", p ->Data);
106        p=p->Next ;
107    }
108    printf("\n");
109}
110
111
112int main() {
113    List ptrl;
114    List index ;
115
116    ptrl = MakeEmpty();
117    ptrl = Insert(1,0,ptrl);
118    ptrl = Insert(2,1,ptrl);
119    ptrl = Insert(3,2,ptrl);
120    ptrl = Insert(4,3,ptrl);
121    //Insert(5,4,ptrl);
122    // Insert(6,5,ptrl);
123    //Insert(6,7,ptrl);
124    Print(ptrl);
125    index = Find(3,ptrl);
126    printf("find %d in list index=%d\n ",3, index->Data);
127    Print(ptrl);
128
129    ptrl = Delete(0,ptrl);
130    Print(ptrl);
131    ptrl = Delete(2,ptrl);
132    Print(ptrl);
133    ptrl = Delete(0,ptrl);
134    Print(ptrl);
135    ptrl = Delete(0,ptrl);
136    Print(ptrl);
137    ptrl = Delete(0,ptrl);
138    Print(ptrl);
139    return 0;
140}
141