动态和静态顺序表【线性表（一）】

线性表实现（一）

线性表可以考虑用顺序表、链表来实现。顺序表可以考虑静态、动态实现。

静态的顺序表有点像数组；

动态的就直接用malloc分配内存。分配完了，操作过程可以跟静态数组差不多，也可以考虑用指针。

具体看代码：

动态顺序表：

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 
  4 #define maxSize 100
  5 typedef int ElemType;
  6 /*typedef struct student 
  7 {
  8     int num;
  9     double score;
 10 }ElemType;
 11 */
 12 typedef struct _Sqlist
 13 {
 14     ElemType *elem;
 15     int length;//元素个数 
 16     int listSize;//空间大小。（最大容量） 
 17 }Sqlist;
 18 /*===================================================*/
 19 void initSqlist(Sqlist *L);/*初始化一个动态的顺序表*/
 20 void insertElem(Sqlist *L,int i,ElemType item);/*在元素个数为length的顺序表L的第i个位置插入新的元素item*/
 21 void delElem(Sqlist *L,int i);/*在元素个数为length的顺序表中删除第i个位置的元素*/
 22 /*===================================================*/
 23 int main()
 24 {
 25     Sqlist a;
 26     ElemType itemToInsert=40;
 27     int i;
 28     initSqlist(&a);
 29     
 30     for(i=0;i<50;i++)
 31     {
 32         a.elem[i]=i+1;
 33         a.length++;
 34     }
 35     
 36     printf("%d
",a.length);
 37     for(i=0;i<a.length;i++)
 38     {
 39         printf("%d ",a.elem[i]);
 40         if((i+1)%10==0)printf("
");
 41     }
 42     
 43     printf("
");
 44     insertElem(&a,40,itemToInsert);
 45     printf("%d
",a.length);
 46     for(i=0;i<a.length;i++)
 47     {
 48         printf("%d ",a.elem[i]);
 49         if((i+1)%10==0)printf("
");
 50     }
 51     
 52     printf("
");
 53     delElem(&a,50);
 54     for(i=0;i<a.length;i++)
 55     {
 56         printf("%d ",a.elem[i]);
 57         if((i+1)%10==0)printf("
");
 58     }
 59     printf("
");
 60     return 0;
 61 }
 62 /*===================================================*/
 63 void initSqlist(Sqlist *L)/*初始化一个动态的顺序表*/
 64 {
 65     L->elem=(ElemType *)malloc(sizeof(ElemType)*maxSize);
 66     if(L->elem==NULL) exit(0);
 67     L->length=0;
 68     L->listSize=maxSize;
 69 }
 70 /*===================================================*/
 71 void insertElem(Sqlist *L,int i,ElemType item)
 72 {/*在元素个数为length的顺序表L的第i个位置插入新的元素item*/
 73     ElemType *base,*insertPtr,*p;
 74     if(i<1||i> L->length+1) exit(0);//插入位置非法.
 75     if(L->length>=L->listSize)
 76     {
 77         base=(ElemType*)realloc(L->elem,(L->listSize+100)*sizeof(ElemType));
 78         //重新追加空间
 79         L->elem=base;
 80         L->listSize=L->listSize+100; 
 81     }
 82     /*
 83     insertPtr=&(L->elem[i-1]);
 84     for(p=&(L->elem[L->length-1]);p>=insertPtr;p--)
 85     {
 86         *(p+1)=*p;
 87     }
 88     *insertPtr=item;
 89     L->length++;
 90     */
 91     i=i-1;//下标从0开始，第i个元素的下标是i-1； 
 92     for(int j=L->length-1;j>=i;j--)
 93     {
 94         L->elem[j+1]=L->elem[j];//因为这里用的是顺序表，其内存是连续的，故可以用中括号下表去直接访问 
 95     }
 96     L->elem[i]=item;
 97     L->length++;
 98 }
 99 /*===================================================*/
100 void delElem(Sqlist *L,int i)
101 {/*在元素个数为length的顺序表中删除第i个位置的元素*/
102     ElemType *delItem,*q;
103     if(i<1 || i> L->length)
104     {
105         exit(0);
106     }
107     delItem=&(L->elem[i-1]);
108     q=L->elem+L->length-1;
109     for(++delItem;delItem<=q;++delItem)
110         *(delItem-1)=*delItem;
111     L->length--;
112 }
113 /*===================================================*/

View Code

静态顺序表：

 1 /*===============================================================
 2 创建一个静态的顺序表存放整数，大小10，完成以下操作：
 3 （1）输入6个整数，打印出顺序表当中的内容，并显示表中剩余的空间个数
 4 （2）在顺序表中的第3个位置插入元素0，打印出顺序表当中的内容并显示
 5 剩余的空间个数
 6 （3）再试图插入表中第11个位置整数0，程序提示超出范围。
 7 （4）删除表中第6个元素，打印出顺序表当中的内容并显示剩余的空间个数 
 8 ===============================================================*/
 9 #include<stdio.h>
10 #define MaxSize 10
11 /*=========================== 
12 向顺序表插入元素
13 参数Sqlist：表首地址
14 参数*len：表长度
15 参数i:插入位置
16 参数x：待插入的元素值 
17 =============================*/
18 void insertElem(int Sqlist[],int *len,int i,int x)
19 {
20     int t;
21     if(*len==MaxSize||i<1||i>*len+1)
22     {
23         printf("This insert is illegal
");//非法插入 
24         return; 
25     }
26     for(t=*len-1;t>=i-1;t--)
27     {
28         Sqlist[t+1]=Sqlist[t];
29     }
30     Sqlist[i-1]=x;//插入元素 
31     *len=*len+1;  //表长加1 
32 }
33 /*=========================== 
34 删除顺序表中的元素
35 参数Sqlist：表首地址
36 参数*len：表长度
37 参数i:删除元素的位置
38 =============================*/
39 void delElem(int Sqlist[],int *len,int i)
40 {
41     int j;
42     if(i<1||i>*len)
43     {
44         printf("This delete is illegal.
");
45         return ;
46     }
47     for(j=i;j<*len;j++)
48         Sqlist[j-1]=Sqlist[j];
49     *len=*len-1;
50 }
51 /*测试代码*/
52 int main()
53 {
54     //按照题目要求进行测试
55     int Sqlist[MaxSize];//定义静态顺序表
56     int len;
57     int i;
58     for(i=0;i<6;i++)
59     {
60         scanf("%d",&Sqlist[i]);
61     }
62     len=6;
63     
64     for(i=0;i<len;i++)
65         printf("%d ",Sqlist[i]);//输出顺序表当中的6个整数
66     printf("
The spare length is %d
",MaxSize-len);//显示剩余空间 
67     
68     insertElem(Sqlist,&len,3,0);//在表中第3个位置插入整数0
69     for(i=0;i<len;i++)
70          printf("%d ",Sqlist[i]);//输出顺序表当中所有整数
71      printf("
The spare length is %d
",MaxSize-len);//显示剩余空间
72      
73      insertElem(Sqlist,&len,11,0);
74      delElem(Sqlist,&len,6);
75      for(i=0;i<len;i++)
76          printf("%d ",Sqlist[i]);//输出顺序表当中所有整数
77      printf("
The spare length is %d
",MaxSize-len);//显示剩余空间
78     return 0;
79 }

View Code