Question

求构建一个线性表的完整程序 数据结构C语言版？？？？

Answer 1

#include "stdafx.h"
#define maxSize 100
typedef int elemType;
#include <stdio.h>
#include <stdlib.h>
typedef int elemType;
struct SeqList {
elemType *list;
int size;
int LmaxSize;
};

/* 初始化线性表L，即进行动态存储空间分配并置L为一个空表 */
void initList(struct SeqList *L, int ms)
{
/* 检查ms是否有效，若无效的则退出运行 */
if(ms <= 0){
printf("MaxSize非法！");
exit(1); /* 执行此函数中止程序运行，此函数在stdlib.h中有定义 */
}
L->LmaxSize = ms; /* 设置线性表空间大小为ms */
L->size = 0;
L->list = (int *)malloc(ms * sizeof(elemType));
if(!L->list){
printf("空间分配失败！");
exit(1);
}
return;
}

/* 空间扩展为原来的2倍，并由p指针所指向，原内容被自动拷贝到p所指向的存储空间 */
void againMalloc(struct SeqList *L)
{
elemType *p = (int *)realloc(L->list, 2 * L->LmaxSize * sizeof(elemType));
if(!p){ /* 分配失败则退出运行 */
printf("存储空间分配失败！ ");
exit(1);
}
L->list = p; /* 使list指向新线性表空间 */
L->LmaxSize = 2 * L->LmaxSize; /* 把线性表空间大小修改为新的长度 */
}

/* 清除线性表L中的所有元素，释放存储空间，使之成为一个空表 */
void clearList(struct SeqList *L)
{
if(L->list != NULL){
free(L->list);
L->list = NULL;
L->size = L->LmaxSize = 0;
}
return;
}
/* 返回线性表L当前的长度，若L为空则返回0 */
int sizeList(struct SeqList *L)
{
return L->size;
}

/* 判断线性表L是否为空，若为空则返回1, 否则返回0 */
int emptyList(struct SeqList *L)
{
if(L->size ==0){
return 1;
}
else{
return 0 ;
}
}

/* 返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行 */
elemType getElem(struct SeqList *L, int pos)
{
if(pos < 1 || pos > L->size){ /* 若pos越界则退出运行 */
printf("元素序号越界！");
exit(1);
}
return L->list[pos - 1]; /* 返回线性表中序号为pos值的元素值 */
}

/* 顺序扫描（即遍历）输出线性表L中的每个元素 */
void traverseList(struct SeqList *L)
{
int i;
for(i = 0; i < L->size; i++){
printf("%d ", L ->list[i]);
printf(" ");
}
return;
}

/* 从线性表L中查找值与x相等的元素，若查找成功则返回其位置，否则返回-1 */
int search(struct SeqList *L, elemType x)
{
int i;
for(i = 0; i < L->size; i++){
if(L->list[i] == x){
return i;
}
}
return -1;
}
/* 把线性表L中第pos个元素的值修改为x的值，若修改成功返回1，否则返回0 */
int updatePosList(struct SeqList *L, int pos, elemType x)
{
if(pos < 1 || pos > L->size){ /* 若pos越界则修改失败 */
return 0;
}
L->list[pos - 1] = x;
return 1;
}

/* 向线性表L的表头插入元素x */
void inserFirstList(struct SeqList *L, elemType x)
{
int i;
if(L->size== L->LmaxSize){ /* 重新分配更大的存储空间 */
againMalloc(L);
}
for(i = L->size - 1; i >= 0; i--)/*元素后移*/
L->list[i + 1] = L ->list[i];
L->list[0] = x;
L->size ++;
}

/* 向线性表L的表尾插入元素x */
void insertLastList(struct SeqList *L, elemType x)
{
if(L->size == L ->LmaxSize){ /* 重新分配更大的存储空间 */
againMalloc(L);
}
L->list[L->size] = x; /* 把x插入到表尾 */
L->size++; /* 线性表的长度增加1 */
return;
}

/* 向线性表L中第pos个元素位置插入元素x，若插入成功返回1，否则返回0 */
int insertPosList(struct SeqList *L, int pos, elemType x)
{
int i;
if(pos < 1 || pos > L->size + 1){ /* 若pos越界则插入失败 */
return 0;
}
if(L->size == L->LmaxSize){ /* 重新分配更大的存储空间 */
againMalloc(L);
}
for(i = L->size - 1; i >= pos - 1; i--){
L->list[i + 1] = L->list[i];
}
L->list[pos - 1] = x;
L->size++;
return 1;
}

/* 向有序线性表L中插入元素x,　使得插入后仍然有序*/
void insertOrderList(struct SeqList *L, elemType x)
{
int i, j;
/* 若数组空间用完则重新分配更大的存储空间 */
if(L->size == L->LmaxSize){
againMalloc(L);
}
/* 顺序查找出x的插入位置 */
for(i = 0; i < L->size; i++){
if(x < L->list[i]){
break;
}
}
/* 从表尾到下标i元素依次后移一个位置， 把i的位置空出来 */
for(j = L->size - 1; j >= i; j--)
L->list[j+1] = L->list[j];
/* 把x值赋给下标为i的元素 */
L->list[i] = x;
/* 线性表长度增加1 */
L->size++;
return;
}
/* 从线性表L中删除表头元素并返回它，若删除失败则停止程序运行 */
elemType deleteFirstList(struct SeqList *L)
{
elemType temp;
int i;
if(L ->size == 0){
printf("线性表为空，不能进行删除操作！ ");
exit(1);
}
temp = L->list[0];
for(i = 1; i < L->size; i++) /* 元素前移 */
L->list[i-1] = L->list[i];
L->size--;
return temp;
}

/* 从线性表L中删除表尾元素并返回它，若删除失败则停止程序运行 */
elemType deleteLastList(struct SeqList *L)
{
if(L ->size == 0){
printf("线性表为空，不能进行删除操作！ ");
exit(1);
}
L->size--;
return L ->list[L->size]; /* 返回原来表尾元素的值 */
}

/* 从线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行 */
elemType deletePosList(struct SeqList *L, int pos)
{
elemType temp;
int i;
if(pos < 1 || pos > L->size){ /* pos越界则删除失败 */
printf("pos值越界，不能进行删除操作！ ");
exit(1);
}
temp = L->list[pos-1];
for(i = pos; i < L->size; i++)
L->list[i-1] = L->list[i];
L->size--;
return temp;
}

/* 从线性表L中删除值为x的第一个元素，若成功返回1，失败返回0 */
int deleteValueList(struct SeqList *L, elemType x)
{
int i, j;
/* 从线性表中顺序查找出值为x的第一个元素 */
for(i = 0; i < L->size; i++){
if(L->list[i] == x){
break;
}
}
/* 若查找失败，表明不存在值为x的元素，返回0 */
if(i == L->size){
return 0;
}
/* 删除值为x的元素L->list[i] */
for(j = i + 1; j < L->size; j++){
L->list[j-1] = L->list[j];
}
L->size--;
return 1;
}

int main(int argc, char* argv[])
{

struct SeqList * ListPerson;
int Listsize=10;
int i;
int num;

ListPerson=(SeqList*)malloc(sizeof(SeqList)); //这句话很重要
initList(ListPerson,Listsize);

for (i=0;i<10;i++)
{
inserFirstList(ListPerson, i);
}

for (i=0;i<5;i++)
{
inserFirstList(ListPerson, i);
}

num=sizeList(ListPerson);

for (i=0;i<num;i++)
{
printf(" %d ", ListPerson->list[i]);
}

printf("\n");
insertPosList(ListPerson, 5, 100);

num=sizeList(ListPerson);

for (i=0;i<num;i++)
{
printf(" %d ", ListPerson->list[i]);
}

return 0;

}

Answer 2

/*~~~~~~~~~~~~~~~~~~顺序表存储结构及常见操作（seqlist.c）~~~~~~~~~~~~~~~~*/
#ifndef __SEQLIST__
#define __SEQLIST__

#include <stdlib.h>
/*顺序表存储空间长度的最小值*/
#define LISTMINSIZE 10
/*顺序表存储结构类型定义*/
typedef struct
{
ListDT *base; /*顺序表空间基地址*/
int listsize; /*顺序表空间尺寸*/
int len; /*顺序表长度*/
}SeqList;

/*顺序表初始化*/
void ListInitialize(SeqList *pL, int size)
{
if(size<LISTMINSIZE)
size=LISTMINSIZE; /*限定不能小于最小尺寸*/
pL->listsize=size;
pL->base=(ListDT *)malloc(pL->listsize*sizeof(ListDT));
if(!pL->base)
exit(EXIT_FAILURE);
pL->len =0; /*初始化空表*/
}

/*按给定的下标取顺序表元素值*/
BOOL ListElem(SeqList L, int index, ListDT *pelem)
{
BOOL flg=TRUE;
if(index<0 || index>L.len-1 )
flg=FALSE; /*参数越界*/
else
*pelem=L.base[index];
return flg;
}

/*求顺序表长度*/
int ListLen(SeqList L)
{
return L.len;
}

/*在顺序表中指定序号位置插入元素*/
BOOL ListInsert(SeqList *pL, int pos, ListDT d)
{
BOOL flg=TRUE;
int i;
if(pos<0 || pL->len>=pL->listsize || pos>pL->len)
flg=FALSE;
else
{
for(i=pL->len-1; i>=pos; i--) /*移动数据*/
pL->base[i+1]=pL->base[i];
pL->base[pos]=d; /*写入数据*/
pL->len++; /*表长增1*/
}
return flg;
}

/*把顺序表中指定序号的元素删除*/
BOOL ListDel(SeqList *pL, int pos)
{
BOOL flg=TRUE;
int i;
if(pos<0 || pos>=pL->len)
flg=FALSE;
else
{
for(i=pos+1; i<pL->len; i++) /*移动数据*/
pL->base[i-1]=pL->base[i];
pL->len--; /*表长增1*/
}
return flg;
}

/*在顺序表中查找元素*/
int ListLoc(SeqList L, ListDT d,BOOL (*equal)(ListDT, ListDT))
{
int pos=L.len-1;
while(pos>=0 && !(*equal)(L.base[pos],d))
pos--;
return pos;
}

/*取前导元素序号位置*/
BOOL ListPrior(SeqList L, int pos, int *ppriorpos)
{
BOOL flg=TRUE;
if(pos>0 && pos<L.len)
*ppriorpos=pos-1;
else
flg=FALSE;
return flg;
}

/*取后继元素序号位置*/
BOOL ListNext(SeqList L, int pos, int *pnextpos)
{
BOOL flg=TRUE;
if(pos>=0 && pos<L.len-1)
*pnextpos=pos+1;
else
flg=FALSE;
return flg;
}

/*销毁顺序表*/
void ListDestroy(SeqList L)
{
free(L.base);
}

#endif
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

/*
建议性测试用程序
*/
typedef enum {TRUE=1,FALSE=0} BOOL;
typedef int ListDT;
#include "seqlist.c"
void printSeqList(SeqList L)
{
int i;
ListDT x;
printf("\nList:\n");
for(i=0; i<ListLen(L); i++)
{
ListElem(L,i,&x);
printf("%3d",x);
}
}

BOOL dataequal(int x, int y)
{
return (x==y)? TRUE:FALSE;
}

#define N 5
void main()
{
int i,prior,next;
ListDT x,test[N]={10,20,30,40,50};
SeqList L;
/*初始化顺序表*/
ListInitialize(&L,N);
/*在表头插入N个元素*/
for(i=0; i<N; i++)
ListInsert(&L,0,test[i]);
printSeqList(L);
/*删除元素*/
ListDel(&L,N/2);
printSeqList(L);
printf("\ninput a key:\n");
scanf("%d",&x);
/*查找x在表中位置*/
i=ListLoc(L,x,dataequal);
/*求x的前导元素*/
if(ListPrior(L,i,&prior))
{
ListElem(L,prior,&x);
printf("Prior:%d\n",x);
}
else
printf("no Prior.\n");
/*求x的后继*/
if(ListNext(L,i,&next))
{
ListElem(L,next,&x);
printf("Next:%d\n",x);
}
else
printf("no Next.\n");
/*求表长*/
printf("List length=%d",ListLen(L));
/*销毁顺序表*/
ListDestroy(L);
}