线性表的顺序表示与实现 |flying0033

winston

/*        线性表是有N个元素的非空有限序列        存在惟一的一个被称作“第一个”数据的元素        存在惟一的一个被称作“第后一个”数据的元素        除第一个与最后一个之外,其它元素都存在唯一的一个前驱和唯一的一个后续        复杂的线性表中的元素可以由多个数据项组成        同一个线性表中的元素类型必须相同        线性表的顺序表,是用一组地址连续的存储单元依次存储线性表的数据元素         算法复杂度:取表长与访问表中的的元素为O(1)，插入与删除的时间复杂度为O(n)        顺序表适用于频繁访问,只有较少（或不进行)“插入删除操作” */

2. #ifndef SQLIST_H
3. #define SQLIST_H
4. #define MAXSIZE  100 //顺序表的最大存储容量
5. #define INFINITY 65535 //设置为β
6. typedef int ElemType;  //顺序表的数据类型,自定义
7. typedef struct {
8.         ElemType data[MAXSIZE]; //定义一个顺序表,大小为MAXSIZE
9.         int len;                                //顺序表的当前长度
10. }SqList;
11. void InitList(SqList *q); //初始化顺序表
12. void GetElem(SqList *q,int i,ElemType *e); //返回元素,将第i个位置的元素存入*e
13. void GetListLength(SqList *q,int *len); //返回顺序表的长度,将长度存入*len
14. void InsertList(SqList *q,int i,ElemType e); //在第i个位置插入e,最坏的情况下i为第一个位置,时间复杂度为O(n)
15. void DeleteList(SqList *q,int i,ElemType *e); //删除第i个位置的元素,将删除的元素存入*e,最坏情况i为第一个位置
16.                                                                                           //时间复杂度为O(n)
17. int LocateElem(SqList *q,ElemType e); //在顺序表中查找元素e是否存在,不存在返回-1，否则返回所在的位置
18. #endif //SQLIST_H
22. #include "SqList.h"
23. #include <stdio.h>
24. #include <string.h>
25. void InitList(SqList *q) //初始化顺序表
26. {
27.         memset(q->data,0,sizeof(ElemType) * MAXSIZE); //初始化顺序表的元素为0
28.         q->len = 0; //初始化顺序表的当前大小为0
29. }
30. void GetElem(SqList *q,int i,ElemType *e) //获取第i个位置的元素(下标值从零开始,i个位置的元素在表中位置为i-1)
31. {
32.         if(i > 0 && i <= q->len) //如果i存在于顺序表中
33.                 *e = q->data[i - 1]; //返回第i个位置的元素
34.         else
35.                 *e = INFINITY; //返回β值
36. }
37. void InsertList(SqList *q,int i,ElemType e) //在顺序表的第i个位置插入元素e
38. {
39.         if(i > MAXSIZE || i <= 0)
40.         {
41.                 printf("超出范围,元素插入失败\n");
42.                 return;
43.         }
44.         for(int j = q->len - 1;j >= i - 1;--j)//将i个位置与i之后的所有元素向后移一位(下标值从零开始i - 1)
45.                 q->data[j + 1] = q->data[j];
46.         q->data[i - 1] = e; //将元素插入到顺序表中,下标值从零开始
47.         ++q->len; //增加当前顺序表的长度值
48. }
49. void DeleteList(SqList *q,int i,ElemType *e) //将顺序表中第i个位置的元素删除,将删除的元素存入*e
50. {
51.         if(i <= 0 && i > q->len)
52.         {
53.                 printf("超出范围,元素删除失败\n");
54.                 *e = INFINITY; //返回β值
55.                 return;
56.         }
57.         *e = q->data[i - 1];
58.         for(int j = i - 1;j < q->len - 1;++j) //第i个位置之后的所有元素向后移
59.                 q->data[j] = q->data[j + 1];
60.         --q->len; //当前的顺序表长度减1
61. }
62. int LocateElem(SqList *q,ElemType e) //在顺序表中查找元素e,如果找到返回位置,否则返回-1
63. {
64.         for(int i = 0;i < q->len;++i)
65.         {
66.                 if(q->data[i] == e)
67.                         return i + 1; //下标从0开始，所以要加上1
68.         }
69.         return -1;
70. }
72. #include "SqList.h"
73. #include <stdio.h>
74. int main()
75. {
76.         SqList q;
77.         InitList(&q); //初始化顺序表
78.         int element;
79.         int i = 1; //插入的位置
80.         printf("请输入要插入顺序表中的内容:(CTRL + Z)结束\n");
81.         while((scanf("%d",&element)) != EOF)
82.         {
83.                 InsertList(&q,i,element);
84.                 ++i;
85.         }
87.         i = 2; //第顺序表的第2个位置插入元素
88.         fflush(stdin); //清空缓冲区,确保输入正确
89.         printf("请输入要在第2个位置插入的元素\n");
90.         scanf("%d",&element);
91.         InsertList(&q,i,element);
93.         printf("顺序表的内容为:\n");
94.         for(int j = 0;j < q.len;++j)
95.                 printf("%d ",q.data[j]);
96.         printf("\n");
98.         int e; //用于存入被删除的元素
99.         printf("请输入要删除的元素的位置\n");
100.         fflush(stdin);
101.         scanf("%d",&i);
102.         DeleteList(&q,i,&e);
103.         printf("被删除的元素为:%d\n",e);
105.         printf("顺序表的内容为:\n");
106.         for(int j = 0;j < q.len;++j)
107.                 printf("%d ",q.data[j]);
108.         printf("\n");
110.         printf("请输入要在表中查找的元素:\n");
111.         fflush(stdin);
112.         scanf("%d",&element);
113.         if((i = LocateElem(&q,element)) == -1)
114.                 printf("顺序表中不存在元素:%d\n",element);
115.         else
116.                 printf("在顺序表的第%d个位置找到元素:%d\n",i,element);
117.         return 0;
118. }

复制代码

作者：flying0033 发表于2011-12-20 11:06:41 原文链接