赞
踩
线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号,其具体含义在不同的情况下一般不同。
在稍复杂的线性表中,一个数据元素可由多个数据项(item)组成,此种情况下常把数据元素称为记录(record),含有大量记录的线性表又称文件(file)。
线性表中的个数n定义为线性表的长度,n=0时称为空表。在非空表中每个数据元素都有一个确定的位置,如用ai表示数据元素,则i称为数据元素ai在线性表中的位序。
线性表的相邻元素之间存在着序偶关系。如用(a1,…,ai-1,ai,ai+1,…,an)表示一个顺序表,则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素。当i=1,2,…,n-1时,ai有且仅有一个直接后继,当i=2,3,…,n时,ai有且仅有一个直接前驱。
初期工作:
- #define OK 1
- #define ERROR 0
- #define OVERFLOW -1
- #define TRUE 1
- #define FALSE 0
-
- #define List_INIT_SPACE 100 //存储空间初始分配量
- #define List_INC_SPACE 10 //存储空间分配增量
-
- typedef int ElemType;//指定顺序表中数据类型
- typedef int Status;
线性表定义:
- typedef struct
- {
- ElemType *elem; //存储空间基址
- int length; //当前长度
- int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)
- }List;
单个线性表的构造、销毁、清空、判空、返回长度、返回定位、返回前驱、返回后继、插入、删除、遍历。
- /*操作结果:构造一个空的线性表。*/
- Status InitList(List &L);
-
- /*初始条件:线性表L已存在。*/
- /*操作结果:销毁线性表L。*/
- Status DestroyList(List &L);
-
- /*初始条件:线性表L已存在。*/
- /*操作结果:将L置为空表。*/
- Status ClearList(List &L);
-
- /*初始条件:线性表L已存在。*/
- /*操作结果:若L为空,则返回TRUE,否则返回FALSE。*/
- Status ListEmpty(List &L);
-
- /*初始条件:线性表L已存在。*/
- /*操作结果:返回L中数据元素个数。*/
- Status ListLength(List &L);
-
- /*初始条件:线性表L已存在,1≤i≤ListLength(L)。*/
- /*操作结果:用e返回L中第i个元素的值。*/
- Status GetElem(List L, int i, Status &e);
-
- /*初始条件:线性表L已存在,compare()是数据元素判断函数。*/
- /*操作结果:返回L中第1个与e满足关系compaer()的数据元素的位序。若这样的数据元素不存在,则返回0。*/
- Status LocateElem(List L, Status e, Status(*compare)(const void *, const void *));
-
- /*初始条件:线性表L已存在。*/
- /*操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义。*/
- Status PriorElem(List L, Status cur_e, Status &pre_e);
-
- /*初始条件:线性表L已存在。*/
- /*操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后续,否则操作失败,next_e无定义。*/
- Status NextElem(List L, Status cur_e, Status &next_e);
-
- /*初始条件:线性表L已存在,1≤i≤ListLength(L)+1。*/
- /*操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1。*/
- Status ListInsert(List &L, int i, Status e);
-
- /*初始条件:线性表L已存在且非空,1≤i≤ListLength(L)。*/
- /*操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1。*/
- Status ListDelete(List &L, int i, Status &e);
-
- /*初始条件:线性表L已存在。*/
- /*操作结果:依次对L的每个数据元素调用函数visit()。一旦visit()操作失败,则操作失败。*/
- Status ListTraverse(List L, Status(*visit)());

- /*构造一个空的线性表L*/
- /*操作结果:构造一个空的线性表。*/
- Status InitList(List &L)
- {
- L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
- if (!L.elem) exit(OVERFLOW);//内存申请失败,异常退出
- L.length = 0;//空表长度为0
- L.listsize = LIST_INIT_SIZE;
- printf("构造一个空的线性表L成功!\n");
- return OK;
- }
- /*销毁线性表L*/
- /*初始条件:线性表L已存在。*/
- /*操作结果:销毁线性表L。*/
- Status DestroyList(List &L)
- {
- if (L.elem)free(L.elem);//释放内存空间
- L.elem = NULL;
- L.length = 0;
- L.listsize = 0;
- return OK;
- }
- /*初始条件:线性表L已存在。*/
- /*操作结果:将L置为空表。*/
- Status ClearList(List &L)
- {
- L.length = 0;
- return OK;
- }
- /*判断线性表是否为空*/
- /*初始条件:线性表L已存在。*/
- /*操作结果:若L为空,则返回TRUE,否则返回FALSE。*/
- Status ListEmpty(List &L)
- {
- if (!L.length)return TRUE;
- else return FALSE;
- }
- /*初始条件:线性表L已存在。*/
- /*操作结果:返回L中数据元素个数。*/
- Status ListLength(List &L)
- {
- return L.length;
- }
- /*初始条件:线性表L已存在,1≤i≤ListLength(L)。*/
- /*操作结果:用e返回L中第i个元素的值。*/
- Status GetElem(List L, int i, Status &e)
- {
- if (i<1 || i>L.length)return ERROR;
- else
- {
- e = L.elem[i - 1];
- return OK;
- }
- }
- /*初始条件:线性表L已存在,compare()是数据元素判断函数。*/
- /*操作结果:返回L中第1个与e满足关系compaer()的数据元素的位序。若这样的数据元素不存在,则返回0。*/
- Status LocateElem(List L, Status e, Status(*compare)(ElemType, ElemType))
- {
- ElemType i, *p;
- i = 1; //i的初值为第一个元素的位序
- p = L.elem; //p的初值为第一个元素的存储位置
- while (i <= L.length&&!(*compare)(*p++, e)) ++i;
- if (i <= L.length)return i;
- else return 0;
- }
- /*初始条件:线性表L已存在。*/
- /*操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义。*/
- Status PriorElem(List L, Status cur_e, Status &pre_e)
- {
- for (int i = 1; i < L.length; i++)
- {
- if (L.elem[i]==cur_e)
- {
- pre_e = L.elem[i - 1];
- return OK;
- }
- else
- {
- if (i >= L.length) return ERROR;
- }
- }
- }

- /*初始条件:线性表L已存在。*/
- /*操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后续,否则操作失败,next_e无定义。*/
- Status NextElem(List L, Status cur_e, Status &next_e)
- {
- for (int i = 0; i < L.length-1; i++)
- {
- if (L.elem[i] == cur_e)
- {
- next_e = L.elem[i + 1];
- return OK;
- }
- else
- {
- if (i >= L.length-1)
- {
- return ERROR;
- }
- }
- }
- }

- /*初始条件:线性表L已存在,1≤i≤ListLength(L)+1。*/
- /*操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1。*/
- Status ListInsert(List &L, int i, Status e)
- {
- ElemType *q, *p, *newbase;
- if (i<1 || i>L.length + 1) return ERROR;//i值不合法
- if (L.length>=L.listsize) //当前存储空间已满,增加分配
- {
- newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType));
- if (!newbase) exit(OVERFLOW); //存储分配失败
- L.elem = newbase; //新基址
- L.listsize += LISTINCREMENT; //增加存储容量
- }
- q = &(L.elem[i - 1]); //q为插入位置
- for (p = &(L.elem[L.length - 1]); p >= q; --p)
- {
- *(p + 1) = *p; //将插入位置及之后的元素右移
- }
- *q = e; //插入e
- ++L.length; //表长增1
- return OK;
- }

- /*初始条件:线性表L已存在且非空,1≤i≤ListLength(L)。*/
- /*操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1。*/
- Status ListDelete(List &L, int i, Status &e)
- {
- ElemType *q, *p;
- if (i<1 || i>L.length)return ERROR; //i值不合法
- p = &(L.elem[i - 1]); //p为被删除元素位置
- e = *p; //将删除元素的值赋给e
- q = L.elem + L.length - 1; //表尾元素的位置
- for (++p; p <= q; ++p) //将被删除元素之后的元素左移
- {
- *(p - 1) = *(p);
- }
- --L.length; //表长减1
- return OK;
-
- }

- /*初始条件:线性表L已存在。*/
- /*操作结果:依次对L的每个数据元素调用函数visit()。一旦visit()操作失败,则操作失败。*/
- Status ListTraverse(List L, Status(*visit)(List L))
- {
- (*visit)(L);
- return OK;
- }
- #include<stdlib.h>
- #include<stdio.h>
-
- #define OK 1
- #define ERROR 0
- #define OVERFLOW -1
- #define TRUE 1
- #define FALSE 0
-
- #define LIST_INIT_SIZE 100 //存储空间初始分配量
- #define LISTINCREMENT 10 //存储空间分配增量
-
- typedef int ElemType;//指定顺序表中数据类型
- typedef int Status;
-
- typedef struct
- {
- ElemType *elem; //存储空间基址
- int length; //当前长度
- int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)
- }List;
-
- /*构造一个空的线性表L*/
- /*操作结果:构造一个空的线性表。*/
- Status InitList(List &L)
- {
- L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
- if (!L.elem) exit(OVERFLOW);//内存申请失败,异常退出
- L.length = 0;//空表长度为0
- L.listsize = LIST_INIT_SIZE;
- printf("构造一个空的线性表L成功!\n");
- return OK;
- }
-
- /*销毁线性表L*/
- /*初始条件:线性表L已存在。*/
- /*操作结果:销毁线性表L。*/
- Status DestroyList(List &L)
- {
- if (L.elem)free(L.elem);//释放内存空间
- L.elem = NULL;
- L.length = 0;
- L.listsize = 0;
- return OK;
- }
-
- /*初始条件:线性表L已存在。*/
- /*操作结果:将L置为空表。*/
- Status ClearList(List &L)
- {
- L.length = 0;
- return OK;
- }
-
- /*判断线性表是否为空*/
- /*初始条件:线性表L已存在。*/
- /*操作结果:若L为空,则返回TRUE,否则返回FALSE。*/
- Status ListEmpty(List &L)
- {
- if (!L.length)return TRUE;
- else return FALSE;
- }
-
- /*初始条件:线性表L已存在。*/
- /*操作结果:返回L中数据元素个数。*/
- Status ListLength(List &L)
- {
- return L.length;
- }
-
- /*初始条件:线性表L已存在,1≤i≤ListLength(L)。*/
- /*操作结果:用e返回L中第i个元素的值。*/
- Status GetElem(List L, int i, Status &e)
- {
- if (i<1 || i>L.length)return ERROR;
- else
- {
- e = L.elem[i - 1];
- return OK;
- }
- }
-
- /*初始条件:线性表L已存在,compare()是数据元素判断函数。*/
- /*操作结果:返回L中第1个与e满足关系compaer()的数据元素的位序。若这样的数据元素不存在,则返回0。*/
- Status LocateElem(List L, Status e, Status(*compare)(ElemType, ElemType))
- {
- ElemType i, *p;
- i = 1; //i的初值为第一个元素的位序
- p = L.elem; //p的初值为第一个元素的存储位置
- while (i <= L.length&&!(*compare)(*p++, e)) ++i;
- if (i <= L.length)return i;
- else return 0;
- }
-
- /*初始条件:线性表L已存在。*/
- /*操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义。*/
- Status PriorElem(List L, Status cur_e, Status &pre_e)
- {
- for (int i = 1; i < L.length; i++)
- {
- if (L.elem[i]==cur_e)
- {
- pre_e = L.elem[i - 1];
- return OK;
- }
- else
- {
- if (i >= L.length) return ERROR;
- }
- }
- }
-
- /*初始条件:线性表L已存在。*/
- /*操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后续,否则操作失败,next_e无定义。*/
- Status NextElem(List L, Status cur_e, Status &next_e)
- {
- for (int i = 0; i < L.length-1; i++)
- {
- if (L.elem[i] == cur_e)
- {
- next_e = L.elem[i + 1];
- return OK;
- }
- else
- {
- if (i >= L.length-1)
- {
- return ERROR;
- }
- }
- }
- }
-
- /*初始条件:线性表L已存在,1≤i≤ListLength(L)+1。*/
- /*操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1。*/
- Status ListInsert(List &L, int i, Status e)
- {
- ElemType *q, *p, *newbase;
- if (i<1 || i>L.length + 1) return ERROR;//i值不合法
- if (L.length>=L.listsize) //当前存储空间已满,增加分配
- {
- newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType));
- if (!newbase) exit(OVERFLOW); //存储分配失败
- L.elem = newbase; //新基址
- L.listsize += LISTINCREMENT; //增加存储容量
- }
- q = &(L.elem[i - 1]); //q为插入位置
- for (p = &(L.elem[L.length - 1]); p >= q; --p)
- {
- *(p + 1) = *p; //将插入位置及之后的元素右移
- }
- *q = e; //插入e
- ++L.length; //表长增1
- return OK;
- }
-
- /*初始条件:线性表L已存在且非空,1≤i≤ListLength(L)。*/
- /*操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1。*/
- Status ListDelete(List &L, int i, Status &e)
- {
- ElemType *q, *p;
- if (i<1 || i>L.length)return ERROR; //i值不合法
- p = &(L.elem[i - 1]); //p为被删除元素位置
- e = *p; //将删除元素的值赋给e
- q = L.elem + L.length - 1; //表尾元素的位置
- for (++p; p <= q; ++p) //将被删除元素之后的元素左移
- {
- *(p - 1) = *(p);
- }
- --L.length; //表长减1
- return OK;
-
- }
-
- /*初始条件:线性表L已存在。*/
- /*操作结果:依次对L的每个数据元素调用函数visit()。一旦visit()操作失败,则操作失败。*/
- Status ListTraverse(List L, Status(*visit)(List L))
- {
- (*visit)(L);
- return OK;
- }
-
- /*初始条件:线性表L已存在。*/
- /*操作结果:输出线性表*/
- Status VisitList(List L)
- {
- for (int i = 0; i < L.length; i++)
- {
- printf("%d ", L.elem[i]);
- }
- return OK;
- }
-
- /*初始条件:线性表L已存在。*/
- /*操作结果:小到大对顺序表进行排序*/
- Status SortList(List &L)
- {
- for (int i = 0; i < L.length - 1; i++)
- {
- for (int j = 0; j < L.length - i - 1; j++)
- {
- if (L.elem[j]>L.elem[j + 1])
- {
- int temp = L.elem[j];
- L.elem[j] = L.elem[j + 1];
- L.elem[j + 1] = temp;
- }
- }
- }
- return OK;
- }
- int main()
- {
- List L;
- ElemType e1, e2;
- Status k;
- int i, a, b, c, d, e, n, j;
- printf("******************\n");
- printf("请选择您所要进行的操作\n");
- printf("1.排序\n");
- printf("2.判断线性表是否为空\n");
- printf("3.线性表中元素的个数\n");
- printf("4.寻找表中第i个元素\n");
- printf("5.寻找指定值前驱\n");
- printf("6.寻找指定值后继\n");
- printf("7.删除元素\n");
- printf("8.遍历输出线性表\n");
- printf("9.清空线性表\n");
- printf("10.销毁线性表\n");
- printf("11.插入元素\n");
- printf("0.退出\n");
- printf("******************\n\n");
- //初始化线性表
- InitList(L);
- printf("初始化表元素个数:");
- scanf("%d", &n);//往线性表插入数据
- printf("输入所插入的数据:");
- for (i = 1; i <= n; i++)
- {
- scanf("%d", &a);
- ListInsert(L, i, a);
- }
- printf("请进行下一步的操作:");
- while (scanf("%d", &c) && c != 0)
- {
- switch (c)
- {
- case 1:
- SortList(L);
- printf("线性表成功由小到大进行排序\n");
- break;
- case 2:
- if (ListEmpty(L)) printf("线性表为空\n");
- else printf("线性表不为空\n");
- break;
- case 3:
- printf("线性表的元素个数为%d\n", ListLength(L));
- break;
- case 4:
- printf("输入要查找表中第i个值:");
- scanf("%d", &i);
- if (i<1 || i>ListLength(L)){
- printf("输入数值错误\n");
- break;
- }
- else{
- GetElem(L, i, e);
- printf("表中第%d个元素对应的数值为%d\n", i,e);
- }
- break;
- case 5:
- printf("输入要查找表中第i个值前驱:");
- scanf("%d", &i);
- if (i < 2 || i >= ListLength(L)) {
- printf("输入数值错误\n");
- break;
- }
- else{
- PriorElem(L, i, e);
- printf("表中第%d个元素对应的前驱数值为%d\n", i, e);
- }
- break;
- case 6:
- printf("输入要查找表中第i个值后继:");
- scanf("%d", &i);
- if (i <= 1 || i > ListLength(L)-1) {
- printf("输入数值错误\n");
- break;
- }
- else{
- NextElem(L, i, e);
- printf("表中第%d个元素对应的后继数值为%d\n", i, e);
- }
- break;
- case 7:
- printf("输入删除元素位序:");
- scanf("%d", &c);
- if (c<1 || c>L.length)
- printf("输入错误!!!元素不存在\n");
- else
- ListDelete(L, c, e);
- printf("删除第%d个元素成功,其值为%d\n", c, e);
- break;
- case 8:
- ListTraverse(L, VisitList);
- printf("\n遍历输出线性表成功!\n");
- break;
- case 9:
- ClearList(L);
- printf("清空成功!\n");
- break;
- case 10:
- DestroyList(L);
- printf("销毁成功!\n");
- break;
- case 11:
- printf("请输入您所想插入的位置以及元素值:");
- scanf("%d%d", &e, &d);
- if (ListInsert(L, e, d)) printf("插入成功!\n");
- else printf("插入失败!\n");
- break;
- default:
- break;
- }
- printf("请进行下一步的操作:");
- }
- printf("成功退出!\n");
- return 0;
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。