数据结构——线性表

一、线性表的抽象数据类型

ADT 线性表（List）

Data

　　线性表的数据对象集合为{a1, a2, … , an}，每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

Operation

　　InitList(*L)：初始化操作，建立一个空的线性表L。

　　ListEmpty(L)：若线性表为空，返回true，否则返回false。

　　ClearList(*L)：将线性表清空。

　　GetElem(L,i,*e)：将线性表L的第i个位置元素返回给e。

　　LocateElem(L,e)：在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号以表示成功，否则返回0表示失败。

　　ListInsert(*L,i,e)：在线性表L中的第i个位置（前）插入新元素e。

　　ListDelete(*L,i,*e)：删除线性表L中第i个位置元素，并用e返回其值。

　　ListLength(L)：返回线性表L的元素个数。

　　ListTraverse(L)：遍历线性表并打印。

endADT

 ==========================2017-9-27补充=================================

问题描述：之前看到这个ADT中的各个操作时，对于调用的形参很是困惑——为什么有些就是传地址，而有些就是传值啊？

问题解决：

　　传值：被调用函数不能修改此形参的值，只能使用它来作为一个“数字”（用来引用）。

　　传地址：被调用函数可以修改此形参的值（因为传地址就是传指针，所以可以修改指针指向的内容）。

　　所以，若我们想改变形参的值时，就需要传地址；而只是引用形参的值时，就可以传值了（传指针好像也没什么错，不过为了防止不小心改变形参值，还是选传值较为妥当）。

=============================补充结束===================================

二、必要概念

结点（Node）：线性表中是这个“结点”，而不是那个“节点”。

线性表的链接存储结构：n个结点 链结 成一个链表，即为线性表（a1,a2,…,an）的链式存储结构。

单链表：当链表的每个结点中只包含一个指针域时。

头指针：链表中的第一个结点的存储位置。（因为指针就是地址啊！）

头结点：在单链表的第一个结点前附设的结点。（头结点的数据域可不存储任何信息，也可以存储如线性表的长度等附加信息；而指针域存储指向第一个结点的指针！）

头结点&头指针：头指针是指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。若线性表为空表，则头结点的指针域为“空”，但是头指针仍指向头结点。

三、线性表的链接存储

1. 单链表的创建

创造单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。

头插法算法思路为：

  1. 声明一指针p；
  2. 初始化一空链表L；
  3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
  4. 循环：生成一新结点赋值给p；随机生成一数字赋值给p的数据域p->data；将p插入到头结点与前一新结点之间。

【头插法】

在这种方法中，新结点始终是第一个结点（位于头结点之后）。

 1 /*    随机产生n个元素的值，建立带表头结点的单链线性表L（头插法）    */
 2 void CreateListHead(List *L, int n)
 3 {
 4     List p;
 5     srand(time(0));                            //初始化随机数种子 
 6     *L = (List)malloc(sizeof(Node));
 7     (*L)->next = NULL;                        //先建立一个带表头结点的单链表 
 8     for(int i=0; i<n; i++){
 9         p = (List)malloc(sizeof(Node));        //生成新结点 
10         p->data = rand()%100+1;                //随机生成100以内的数字 
11         p->next = (*L)->next;
12         *(L)->next = p;                        //插入到表头 
13     }
14 }
View Code

【尾插法】

这才是正常的思维，新结点总是放在表的最后。

 1 /*    随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）    */
 2 //L是指整个单链表，而r是指向尾结点的变量
 3 //r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表 
 4 void CreateListTail(List *L, int n)
 5 {
 6     List p, r;
 7     srand(time(0));                            //初始化随机数种子 
 8     *L = (List)malloc(sizeof(Node));        //为整个线性表 
 9     r = *L;                                    //r为指向尾部的结点 
10     for(int i=0; i<n; i++){
11         p = (List)malloc(sizeof(Node));        //生成新结点 
12         p->data = rand()%100+1;                //随机生成100以内的数字 
13         r->next = p;                        //将表尾终端结点的指针指向新结点 
14         r = p;                                //将当前的新结点定义为表尾终端结点 
15     }
16     r->next = NULL;                            //表示当前链表结束 
17 }
View Code

2. 完整代码

/*	线性表的顺序存储	*/
//线性表的序号从1开始 
#include <cstdio>
#include <ctime>
#include <malloc.h>

typedef int ElemType;

typedef struct node{
	ElemType data;
	struct node * next;
}Node;

typedef Node * List;

/*	将线性表L的第i个位置元素返回给e	*/
bool GetElem(List L, int i, ElemType *e)
{
	List p;
	p = L->next;	//让p指向链表L的第一个结点 
	int pos = 1;
	while(p && pos < i){
		p = p->next;
		pos++;
	} 
	if(!p || pos > i)	//第i个结点不存在  
		return false;
	*e = p->data;
	return true;
} 

/*	在线性表L中的第i个位置（前）插入新元素e	*/
bool ListInsert(List *L, int i, ElemType e)
{
	List p, s;
	p = *L;		//L是二重指针
	int pos = 1;
	while(p && pos < i){
		p = p->next;
		pos++;
	}
	if(!p || pos>i)
		return false;
	s = (List)malloc(sizeof(Node));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
} 

/*	删除线性表L中第i个位置元素，并用e返回其值	*/
bool ListDelete(List *L, int i, ElemType *e)
{
	List p, q;
	p = *L;
	int pos = 1;
	while(p->next && pos < i){
		p = p->next;
		pos++;
	}
	if(!(p->next) || pos > i)
		return false;
	*e = q->data;
	q = p->next;
	p->next = q->next;
	free(q);		//释放内存 
	return true;
}

/*	随机产生n个元素的值，建立带表头结点的单链线性表L（头插法）	*/
/*
void CreateListHead(List *L, int n)
{
	List p;
	srand(time(0));							//初始化随机数种子 
	*L = (List)malloc(sizeof(Node));
	(*L)->next = NULL;						//先建立一个带表头结点的单链表 
	for(int i=0; i<n; i++){
		p = (List)malloc(sizeof(Node));		//生成新结点 
		p->data = rand()%100+1;				//随机生成100以内的数字 
		p->next = (*L)->next;
		*(L)->next = p;						//插入到表头 
	}
}
*/

/*	随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）	*/
//L是指整个单链表，而r是指向尾结点的变量
//r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表 
void CreateListTail(List *L, int n)
{
	List p, r;
	srand(time(0));							//初始化随机数种子 
	*L = (List)malloc(sizeof(Node));		//为整个线性表 
	r = *L;									//r为指向尾部的结点 
	for(int i=0; i<n; i++){
		p = (List)malloc(sizeof(Node));		//生成新结点 
		p->data = rand()%100+1;				//随机生成100以内的数字 
		r->next = p;						//将表尾终端结点的指针指向新结点 
		r = p;								//将当前的新结点定义为表尾终端结点 
	}
	r->next = NULL;							//表示当前链表结束 
}

/*	将单链表清空	*/
void ClearList(List *L)
{
	List p, q;
	p = (*L)->next;				//p指向第一个结点 
	while(p){					//没到表尾 
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;			//头结点指针域为空 
}

int ListLength(List L){
    int cnt = 0; 		//计数器
    while(L->next){
        L = L->next;
        cnt++;
    } 
    return cnt;
} 

/*	遍历单链表并打印	*/ 
void ListTraverse(List L){
    if(L->next == NULL){
        printf("链表为空!");
    }else{
        List p;
        p = L->next;
        while(p != NULL){
            printf("%d ",p->data);
            p = p->next;
        }
        printf("
");   
    }
}

void read()
{
	List L;
	CreateListTail(&L,10);
	printf("初始化10个元素,分别是: 
"); 
    ListTraverse(L);
    ElemType e; 
    GetElem(L, 4, &e);
    printf("链表中第4个元素是: %d 
",e); 
    printf("链表的长度是: %d 
",ListLength(L));
    ListInsert(&L, 4, 12);
    printf("在链表第4个元素之前插入12 
"); 
    ListTraverse(L);
    ListDelete(&L, 5, &e);
    printf("在链表中删除第5个元素 
"); 
    ListTraverse(L);
    ClearList(&L);
    printf("清除链表之后的元素: 
"); 
    ListTraverse(L);
}

int main()
{
	read();
	return 0;
}

三、线性表的顺序存储

1. 完整代码

  1 /*线性表功能的实现*/
  2 #include<stdio.h>
  3 
  4 //定义常量 存储空间的初始化分配
  5 #define MAXSIZE 20
  6 #define TRUE 1
  7 #define ERROR -1
  8 #define FALSE 0
  9 #define OK 1
 10 
 11 //用typedef定义类型
 12 typedef int Status;
 13 typedef int ElemType;
 14 //定义一个结构体类型
 15 typedef struct{
 16     ElemType data[MAXSIZE];
 17     int length;
 18 } SqList; 
 19 
 20 //初始化函数
 21 Status initList(SqList *L){
 22     L->length = 0;
 23     return OK; 
 24 } 
 25 
 26 //返回线性表的长度
 27 Status getListLength(SqList L){
 28     return L.length;
 29 }
 30 
 31 //线性表为空返回true,否则返回false
 32 Status listEmpty(SqList L){
 33     if(L.length == 0){
 34         return TRUE; 
 35     }
 36     return FALSE;
 37 } 
 38 
 39 //线性表清空,长度为0 
 40 Status clearList(SqList *L){
 41     L->length = 0; 
 42     return OK;
 43 } 
 44 //获取指定的元素的值,返回下标为i - 1的元素,赋值给e
 45 Status getElem(SqList L, int i, ElemType *e){
 46     //判断元素位置是否合法[i]
 47     if(i > L.length || i < 1){
 48         printf("查找的位置不正确 
");
 49         return ERROR; 
 50     }
 51     //判断线性表是否为空
 52     if(listEmpty(L)){
 53         return ERROR;
 54     } 
 55     *e = L.data[i - 1];
 56     return OK;
 57 }
 58 
 59 //在线性表中查找指定的e相等的元素,如果查找成功,返回该元素的下标,否则返回ERROR
 60 Status locateElem(SqList L, ElemType e){
 61     int i;
 62     for(i = 0; i < L.length - 1; i++){
 63         if(L.data[i] == e){
 64             return i;
 65         }
 66     }
 67     printf("没有查找到元素 %d 指定的下标
",e);
 68     return ERROR;
 69 } 
 70 
 71 //自动创建 MAXSIZE 个元素,并赋值为0 
 72 Status createList(SqList *L){
 73     int i;
 74     for(i = 0; i < 10; i++){
 75         L->data[i] = 0;
 76     } 
 77     L->length = 10;
 78     return OK;
 79 } 
 80 
 81 //在线性表中第i个位置前插入新元素e 
 82 Status listInsert(SqList *L, int i, ElemType e){
 83     //判断长度是否可以允许插入新的数据 
 84     if(L->length >= MAXSIZE){
 85         printf("空间已满,不能再插入数据
");
 86         return FALSE; 
 87     }
 88     //判断插入位置的合法性
 89     if(i < 1 || i > L->length) {
 90         printf("插入位置不正确
");
 91         return FALSE;
 92     }
 93     int j;
 94     for(j = L->length - 1; j >= i; j--){
 95         L->data[j] = L->data[j - 1];
 96     }
 97     L->data[i - 1] = e;
 98     L->length++;
 99     return TRUE;
100 }
101 
102 //删除线性表中第i个元素,成功后表长减1,用e返回其值 
103 Status deleteList(SqList *L, int i, ElemType *e){
104     //判断线性表是否为空
105     if(listEmpty(*L)){
106         return ERROR;
107     }
108     //判断删除的位置是否合法
109     if(i < 1 || i > L->length) {
110         printf("删除位置不合法
");
111         return ERROR;
112     }
113     *e = L->data[i - 1];
114     for(i; i < L->length; i++){
115         L->data[i - 1] = L->data[i];
116     }
117     L->length--;
118     return TRUE;
119 } 
120 
121 //遍历线性表
122 Status listTraverse(SqList L){
123     int i;
124     for(i = 0; i < L.length; i++){
125         printf("%d ",L.data[i]);
126     }
127     printf("
");
128     return OK;
129 } 
130 
131 //主程序
132 int main(void){
133     SqList L;
134     ElemType e;
135     initList(&L);
136     int option = 1;
137     int input_number;
138     int res;
139     ElemType input_value;
140     printf("
1.遍历线性表 
2.创建线性表 
3.清空线性表 
4.线性表插入 
5.查找表中元素 
6.判断元素是否在表中 
7.删除某个元素 
8.线性表长度
9.线性表是否为空
0.退出 
请选择你的操作：
");
141     while(option){
142         scanf("%d",&option);
143         switch(option){
144             case 0:
145                 return OK;
146                 break;
147             case 1:
148                 listTraverse(L);
149                 break;
150             case 2:
151                 createList(&L);
152                 listTraverse(L);
153                 break;
154             case 3:
155                 clearList(&L);
156                 listTraverse(L);
157                 break; 
158             case 4:
159                 printf("请输入插入的位置:");
160                 scanf("%d",&input_number); 
161                 printf("
"); 
162                 printf("请输入插入的值:");
163                 scanf("%d",&input_value); 
164                 printf("
");
165                 listInsert(&L, input_number, input_value);
166                 listTraverse(L);
167                 break;
168             case 5:
169                 printf("请输入要查找的位置:");
170                 scanf("%d",&input_number);
171                 printf("
");
172                 getElem(L, input_number, &input_value);
173                 printf("第%d个元素的值为:%d
",input_number,input_value);
174                 break; 
175             case 6:
176                 printf("请输入要查找的元素:");
177                 scanf("%d",&input_value);
178                 printf("
");
179                 res = locateElem(L, input_value);
180                 if(res != ERROR){
181                     printf("值为%d在表中的第%d个位置
",input_value,input_number);
182                 }
183                 break; 
184             case 7:
185                 printf("要删除第几个元素？");
186                 scanf("%d",&input_number); 
187                 printf("
");
188                 deleteList(&L, input_number, &input_value);
189                 listTraverse(L);
190                 break;
191             case 8:
192                 res = getListLength(L);
193                 printf("线性表的长度是:%d",res);
194                 break;
195             case 9:
196                 res = listEmpty(L);
197                 if(res){
198                     printf("线性表的是空的");
199                 }else{
200                     printf("线性表的是不是空的");
201                 } 
202                 break;
203         }
204     }
205     return OK;
206 }
View Code 
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/xzxl/p/7545984.html