C语⾔实现顺序表的基本操作（从键盘输⼊⽣成线性表，读txt⽂件⽣成线性表和数组⽣成线性表-。。。
经过三天的时间终于把顺序表的操作实现搞定了。（主要是在测试部分停留了太长时间）
1. 线性表顺序存储的概念：指的是在内存中⽤⼀段地址连续的存储单元依次存储线性表中的元素。
2. 采⽤的实现⽅式：⼀段地址连续的存储单元可以⽤固定数组或者动态存储结构来实现，这⾥采⽤动态分配存储结构。
3. 顺序表结构体⽰意图
三种写法完整代码：
第⼀种写法. 从键盘输⼊⽣成线性表--完整代码如下，取值操作实际上就是删除操作的部分实现，这⾥就不写了
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;
typedef struct SqList
{
ElemType *elem;
int length;
int listsize;
}SqList;
Status InitList(SqList &L)
{
L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem)
{
printf("ERROR\n");
return ERROR;
}
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
Status ListEmpty(SqList L) //判空
{
if (L.length = 0) return TRUE;
else return FALSE;
}
Status ListInsert(SqList &L, int i, ElemType e) //插⼊
{
ElemType *p, *q;
ElemType *newbase;
int j;
if (i < 1 || i > L.length + 1) return ERROR;
if (L.length >= L.listsize){
newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
if (newbase == NULL)
{
printf("realloc failed!\n");
return ERROR;//exit(-1);
}
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
p = L.elem+i-1;
for( q = L.elem + L.length - 1; q>= p; --q )
{
*(q+1) = *q;
}
*p = e;
++L.length;
return OK;
}
Status CrtList(SqList &L) // 从键盘输⼊数据⽣成线性表
{
printf("输⼊整数，以0结束:\n");
ElemType e;
int i = 1;
scanf("%d", &e);
while (e != 0)
{
if (!ListInsert(L, i, e)) return ERROR;
i++;
scanf("%d", &e);
}
return OK;
}
Status CrtList2(SqList &L, ElemType d[], int n) // 从数组⽣成线性表
{
int i;
for (i = 0; i < n; ++i)
{
if (!ListInsert(L, i + 1, d[i])) return ERROR;
}
return OK;
}
Status ListDelet(SqList &L, int i, ElemType &e) //删除
{
if ((i<1) || (i>L.length)) return ERROR;
ElemType *p, *q;
p = &(L.elem[i - 1]);
e = *p;
q = L.elem + L.length - 1;
for (++p; p <= q; ++p) *(p - 1) = *(p);
--L.length;
return OK;
}
Status GetElem(SqList &L, int i, ElemType &e) //取值
{
if ((i <= 0) || (i>L.length)) return ERROR;
else
{
e = L.elem[i - 1];
return OK;
}
}
Status compare(ElemType a, ElemType b) //⽐较
{
if (a == b) return TRUE;
else return FALSE;
}
int LocateElem(SqList L, ElemType e) //定位
{
Status compare(ElemType a, ElemType b);
int i;
for (i = 0; i<L.length; i++)
{
if (compare(L.elem[i], e))
return ++i;
}
if (i == L.length) return0;
}
Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e) //求直接前驱{
int LocateElem(SqList L, ElemType e);
int i = LocateElem(L, cur_e);
if ((i == 0) || (i == 1)) return ERROR;
pre_e = L.elem[i - 2];
return OK;
}
int ListLength(SqList L) //求长度
{
int length = L.length;
return length;
}
void MergeList(SqList La, SqList Lb, SqList &Lc) //归并
{
Lc.length = La.length + Lb.length;
Lc.listsize = Lc.length;
Lc.elem = (ElemType*)malloc(Lc.length*sizeof(ElemType));
if (Lc.elem == NULL) exit(OVERFLOW);
int i, j, k;
for (i = 0, j = 0, k = 0; (i<La.length) && (j<Lb.length); k++)
{
if (La.elem[i]<Lb.elem[j])
{
Lc.elem[k] = La.elem[i];
i++;
}
else
{
Lc.elem[k] = La.elem[j];
j++;
}
}
while (i<La.length)
{
Lc.elem[k] = La.elem[i];
i++;
k++;
}
while (j<Lb.length)
{
Lc.elem[k] = Lb.elem[j];
j++;
k++;
}
}
void vist(ElemType e)
{
printf("%d ", e);
}
Status ListTraverse(SqList L) //遍历
{
int i;
if (L.length == 0) printf("⽆元素");
for (i = 0; i<L.length; i++)
{
vist(L.elem[i]);
}
if (i == L.length)
{
printf("\n");
return OK;
}
else return ERROR;
}
Status ListClear(SqList L) //清空
{
if (L.elem == NULL) return ERROR;
int i;
for (i = 0; i<L.length; i++) L.elem[i] = 0;
L.length = 0;
return OK;
}
Status DestroyList(SqList &L) //销毁
{
if (L.elem == NULL) return ERROR;
free(L.elem);
L.length = 0;
L.listsize = 0;
return OK;
}
void PrnList(SqList L) //打印
{
int i;
for (i = 0; i < L.length; ++i){
printf("%5d", L.elem[i]);
}
printf("\n");
}
int main()
{
int j, l;
ElemType e, e1;
SqList La;
if (InitList(La)) printf("OK\n");
else exit(INFEASIBLE);
CrtList(La);
PrnList(La);
int k;
printf("1：判空\n2：插⼊\n3：删除\n4：定位\n5：求长度\n6：直接前驱\n");
printf("7：归并\n8：遍历\n9：清空\n10：销毁\n\n0：退出\n");
scanf("%d", &k);
while (k != 0)
{
switch (k)
{
case1:
if (ListEmpty(La)) printf("empty\n");
else printf("non-empty\n");
break;
case2:
printf("在第⼏个位置插⼊何数：");
scanf("%d%d", &j, &e);
if (ListInsert(La, j, e)) printf("OK\n");
else printf("ERROR\n");
break;
case3:
printf("删除第⼏个数：");
scanf("%d", &j);
if (ListDelet(La, j, e))
PrnList(La);
printf("删除数为：%d\n", e);
break;
case4:
printf("定位数字：");
scanf("%d", &e);
if (LocateElem(La, e) != 0) printf("OK，位序为：%d\n", LocateElem(La, e));
else printf("ERROR\n");
break;
case5:
l = ListLength(La);
printf("ListLength=%d\n", l);
break;
case6:
printf("寻何数直接前驱:");
scanf("%d", &e);
if (PriorElem(La, e, e1)) printf("前驱为:%d\n", e1);
else printf("ERROR\n");
break;
case7:
SqList Lb, Lc;
if (InitList(Lb)) printf("OK\n");
else printf("ERROR\n");
CrtList(Lb);
MergeList(La, Lb, Lc);
printf("有序归并后：\n");
PrnList(Lc);
break;
case8:
if (ListTraverse(La)) printf("遍历成功\n");
else printf("遍历失败\n");
break;
case9:
if (ListClear(La)) printf("清空成功\n");
else printf("清空失败\n");
break;
case10:
if (DestroyList(La)) printf("销毁完成\n");
else printf("销毁失败\n");
return0;
default:
printf("ERROR\n");
}
scanf("%d", &k);
}
return0;
}
View Code
第⼆种写法. 从txt⽂件读⼊⽣成线性表--完整代码如下：
#include<stdio.h>
#include<stdlib.h>
#define OK 1
c语言写入txt文件#define ERROR 0
#define OVERFLOW -1
#define TRUE 1
#define FALSE 0
#define INIT_LIST_SIZE 100
#define LISTINCREMENT 10
typedef int Status;
typedef int ElemType;
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
Status InitList(SqList *L)
{
L->elem = (ElemType*)malloc(INIT_LIST_SIZE*sizeof(ElemType));
if (!L->elem) exit(OVERFLOW);
L->length = 0;
L->listsize = INIT_LIST_SIZE;
return OK;
}
Status ListEmpty(SqList L) //判空
{
if (L.length = 0) return TRUE;
else return FALSE;
}
Status ListInsert(SqList *L, int i, ElemType e) //插⼊
{
ElemType *newbase, *q, *p;
if (i<1 || i>L->length + 1) return ERROR;
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;
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论