首页 > > 程序设计 > C/C++ >

1）链表顺序存储---之二代码

2018-06-18 04:16:29来源：未知阅读 ()

参考文档：

1）《《大话数据结构》》

2）http://blog.chinaunix.net/uid-20680669-id-147844.html

3）http://blog.csdn.net/strommaybin/article/details/51919464

1. 线性表（list）：零个或多个数据元素的有限序列

线性表（Linear_list）是最常用也是最简单的数据结构。简言之，一个线性表是n个数据元素的有限序列。线性表是有线性结构的表。什么是线性结构呢？线性结构是n个数据元素的有序集合。它有四个基本特征：
　　1．集合中必存在唯一的一个”第一个元素”；
　　2．集合中必存在唯一的一个”最后的元素”；
　　3．除最后元素之外，其它数据元素均有唯一的”后继”；
　　4．除第一元素之外，其它数据元素均有唯一的”前驱”。
　　如（a1,a2,a3,…..,an）,a1为第一个元素，an为最后一个元素，此集合极为一个线性结构的集合。
　　相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后驱。
　　常用的线性结构有：线性表，栈，队列，双队列，数组，链表，串。

2. 功能及实现：

结构体的定义
初始化
尾部插入值为x的节点
打印各节点的值
判断节点是否为空
查找值为x的节点的位置
取得i节点的值
在i位置插入x值
删除i位置的节点

  1 typedef int Status;
  2 
  3 
  4 //1. 结构体的定义：
  5 #define MAXSIZE 100
  6 typedef int ElemType;
  7 
  8 //结构体的定义
  9 typedef struct list
 10 {
 11     ElemType data[MAXSIZE];//数据
 12     int length ;            //线性表的当前长度
 13 } sqlist;
 14 
 15 
 16 //2. 初始化
 17 sqlist * init_sqlist()
 18 {
 19     //tmp=(TSeqList*)malloc(sizeof(TSeqList));//分配空间
 20     sqlist *list=(sqlist*)malloc(sizeof(sqlist));
 21     list->length=0;
 22     return list;
 23 }
 24 
 25 //3.尾部插值
 26 int  insert_rear_sqlist(sqlist *list,ElemType data)
 27 {
 28     int ret=0;
 29     if(list->length==MAXSIZE||list->length==0)
 30     {
 31         ret=-1;
 32         printf("func insert_rear_sqlist erro: %d",ret);
 33         return -1;
 34     }
 35     list->length=list->length++;//长度+1
 36     list->data[list->length]=data;//插入数据
 37     return 0;
 38 }
 39 
 40 // 4. 打印节点的值
 41 int print_sqlist(sqlist *list)
 42 {
 43     int ret=-1;
 44     if(list->length==0)
 45     {
 46         printf("\nThe list is empty: %d \n",ret);
 47         return ret;
 48     }
 49     
 50     else
 51     {
 52         for(int i=0;i<list->length;i++)
 53             printf("%5d\n",list->data[i]);
 54     }
 55     return 0;
 56 }
 57 
 58 //5. 判断是否为空
 59 int is_empty_sqlist(sqlist *list)
 60 {
 61     return list->length==0?0:1;
 62 }
 63 
 64 //6. 查找值为x的节点的 位置(有问题 待改正)
 65 int find_num_sqlist(sqlist* list,ElemType data)
 66 {
 67     int ret=0;
 68     int temp=0;
 69     if(list->length==MAXSIZE||list->length==0)
 70     {
 71         ret=-1;
 72         printf("func insert_rear_sqlist erro: %d",ret);
 73         return -1;
 74     }
 75     for (int i=0;list->length<MAXSIZE;i++)
 76     {
 77         if(list->data[i]==data)
 78             temp=i;
 79     }
 80     
 81     return temp;
 82 }
 83 
 84 //7. 取得i节点的值
 85 int get_elem(sqlist *list,int i)
 86 {
 87     if(list->length<=0||i<0||i>list->length)
 88     {
 89         return -1;
 90     }
 91     return list->data[i];
 92 }
 93 
 94 // 8.  在i位置插入e值
 95 int insert_list(sqlist *list,int i,ElemType e)
 96 {
 97     int k=0,ret=0;
 98     if(list->length==MAXSIZE)
 99     {
100         ret=-1;
101         printf("insert_list erro :%d ",ret);
102     }
103     if(i<0||i>list->length||list->length>MAXSIZE)
104     {
105         ret=-2;
106         printf("insert_list erro :%d ",ret);
107     }
108     
109         for (k=list->length;k>=i;k--)
110         {
111             list->data[k]=list->data[k-1];//元素后移
112         }
113         list->data[i]=e;
114         list->length++;
115     
116     return 0;
117 }
118 
119 //9. 删除i位置的节点
120 int delete_list(sqlist *list,int i,ElemType *e)
121 {
122     int k=0;
123     int ret=0;
124     if(list->length==0)
125     {
126         ret=-1;
127         printf("delete_list erro: %d",ret);
128     }
129     if(i<0||i>list->length)
130     {
131         ret=-1;
132         printf("delete_list erro: %d",ret);
133     }
134 //    if(i<list->length)
135     //{
136         *e=list->data[i];
137         for(k=i;k<=list->length;k++)
138         {
139             list->data[k]=list->data[k+1];//元素前移
140         }
141     //}
142     list->length--;
143     return 0;
144 }

　---------------------------------------

3. 测试代码

 1 int main()
 2 {
 3     int ret=0;
 4     int t1=1;
 5     int t2=2;
 6     int t3=3;
 7     int t4=4;
 8     int t5=5;
 9 
10     //sqlist *list;
11     //void init_sqlist(sqlist *list)
12     sqlist *list=init_sqlist();
13 
14     //cout<<sizeof(*list);
15     //int insert_list(sqlist *list,int i,ElemType e);
16     //1. 头插法
17     ret=insert_list(list,0,t1);
18     ret=insert_list(list,0,t2);
19     ret=insert_list(list,0,t3);
20     ret=insert_list(list,0,t4);
21     ret=insert_list(list,0,t5);
22     
23     //2. 打印 遍历
24     //int print_sqlist(sqlist *list)
25     printf("插入数据: \n");
26     ret=print_sqlist(list);
27     int tmp=0;
28     
29     //3. 删除链表中所有的节点
30     printf("\n删除节点数据: \n");
31     while(list->length>0)
32     {
33         //int delete_list(sqlist *list,int i,ElemType *e)
34         ret=delete_list(list,0,&tmp);
35         printf("%5d\n",tmp);
36     }
37 
38     //5. 判断是否为空
39     //int is_empty_sqlist(sqlist *list)
40     ret=is_empty_sqlist(list);
41     printf("链表是否为空%5d\n",ret);
42 
43     system("pause");
44     return 0;
45 }