Question

线性表的基本操作

A. 初始化线性表
B. 调用插入函数建立一个线性表
C. 在线性表中查找指定值的元素
D. 在线性表中删除指定位置的元素
E. 遍历并输出线性表

Answer 1

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
# define null 0
typedef char ElemType; /* 字符型数据*/
typedef struct LNode
{
ElemType data;
struct LNode *next;
};
void setnull(struct LNode **p);
int length (struct LNode **p);
ElemType get(struct LNode **p,int i);
void insert(struct LNode **p,ElemType x,int i);
int locate(struct LNode **p,ElemType x);
void Delete(struct LNode **p,int i);
void display(struct LNode **p);
struct LNode * reverse(struct LNode **head);

main()
{
struct LNode *head; /*定义变量*/
int select,x1,x2,x3;
int i,n;
int m,g;
char e,y;

setnull(&head); /*建一链表并设置为空表*/

printf("请输入数据长度: ");
scanf("%d",&n);
printf("将数据插入到单链表中: ");
for(i=1;i<=n;i++)
{

scanf("%c",&y);
if(y=='\n') i--;
else {
printf("将数据插入到单链表中: ");
insert(&head,y,i);
}
} /*插入数据到链表*/

display(&head); /*显示链表所有数据*/

printf("select 1 求长度 length()\n");
printf("select 2 取结点 get()\n");
printf("select 3 求值查找 locate()\n");
printf("select 4 删除结点 delete()\n");
printf("select 5 链表反转 reverse（)\n");
printf("input your select: ");
scanf("%d",&select);
switch(select)
{
case 1:
{
x1=length(&head);
printf("输出单链表的长度%d\n ",x1);
display(&head);
}break;

case 2:
{
printf("请输入要取得结点: ");
scanf("%d",&m);
x2=get(&head,m);
printf("%c\n",x2);
display(&head);
}break;

case 3:
{
printf("请输入要查找的数据: ");
scanf("\n%c",&e);
x3=locate(&head,e);
printf("%d\n",x3);
display(&head);
}break;

case 4:
{
printf("请输入要删除的结点: ");
scanf("%d",&g);
Delete(&head,g);

display(&head);
}break;
case 5:
{
printf("链表反转:");
reverse(&head);
display(&head);
}break;

}
}
void setnull(struct LNode **p)
{

*p=null;

}
int length (struct LNode **p)
{
int n=0;
struct LNode *q=*p;
while (q!=null)
{
n++;
q=q->next;
}
return(n);
}
ElemType get(struct LNode **p,int i)
{
int j=1;
struct LNode *q=*p;

while (j<i&&q!=null)
{
q=q->next;
j++;
}

if(q!=null)
return(q->data);
else
printf("位置参数不正确!\n");
return null;
}
int locate(struct LNode **p,ElemType x)
{
int n=0;
struct LNode *q=*p;
while (q!=null&&q->data!=x)
{
q=q->next;
n++;
}
if(q==null)
return(-1);
else
return(n+1);
}
void insert(struct LNode **p,ElemType x,int i)
{
int j=1;
struct LNode *s,*q;
q=*p;
s=(struct LNode *)malloc(sizeof(struct LNode));
s->data=x;

if(i==1)
{
s->next=q;
*p = s;
}
else
{
while(j<i-1&&q->next!=null)
{
q=q->next;
j++;
}
if(j==i-1)
{
s->next=q->next;
q->next=s;
}
else
printf("位置参数不正确!\n");
}
}
void Delete(struct LNode **p,int i)
{
int j=1;
struct LNode *q=*p,*t=null;
if(i==1)
{
t=q;
*p=q->next;

}
else
{
while(j<i-1&&q->next!=null)
{
q=q->next;
j++;
}
if(q->next!=null&&j==i-1)
{
t=q->next;
q->next=t->next;
}
else
printf("位置参数不正确!\n");
}
if(t=null)
free(t);
}
void display(struct LNode **p)
{
struct LNode *q;
q=*p;
printf("单链表显示: ");
if(q==null)
printf("链表为空!");
else if (q->next==null)
printf("%c\n",q->data);
else
{
while(q->next!=null)
{
printf("%c->",q->data);
q=q->next;
}
printf("%c",q->data);
}
printf("\n");
}

struct LNode * reverse(struct LNode **head)
{
struct LNode *p,*q;

p=null;
while((*head)->next!=null)
{
q=p;
p=*head;
(*head)=(*head)->next;
p->next=q;

}
(*head)->next=p;
return *head;
}

Answer 2

/*线性表的操作*/
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
struct List
{
ElemType *list;
int size;
int MaxSize;
};

/*初始化列表,即动态存储空间分配并置L为一个空列表*/
void initList(struct List *L,int ms)
{
if(ms<=0)
{
printf("MaxSize 非法！");
exit(1);
}
L->MaxSize = ms;
L->size = 0;
L->list=malloc(ms * sizeof(ElemType));
if(!L->list)
{
printf("空间分配失败！");
exit(1);
}
/*printf("%d\n",sizeof(ElemType));*//*暂用字节数*/
return ;
}
void againMalloc(struct List *L)
{
ElemType *p = realloc(L->list,2*L->MaxSize*sizeof(ElemType));
if(!p)
{
printf("存储空间分配失败！");
exit(1);
}
L->list = p; /*使list指向新线性表空间*/
L->MaxSize=2 * L->MaxSize; /*把线性空间大小修改为新的长度*/
}
/*向线性表L的表尾插入元素*/
void insertLastList(struct List *L,ElemType x)
{
if(L->size==L->MaxSize){
/*重新分配更大空间*/
/*againMalloc(L);*/
printf("max\n");
}
L->list[L->size]= x ;
L->size++;
printf("x=%d\n" ,x);
return ;
}

/*插入内容*/
int insertPostList(struct List *L,int pos,ElemType x)
{
int i;
if(pos<1 || pos> L->size+1)
{
/* 若Pos越界则插入失败 */
return 0 ;
}
if(L->size==L->MaxSize){
/*重新分配更大的存储空间*/
againMalloc(L);
}
L->list[pos-1] = x;
L->size++;
/* printf("%d\n", L->list[pos-1] ); */
return 1 ;
}
/* 按下标获得元素值 */
ElemType GetElem(struct List *L ,int pos)
{
if(pos<1 || pos>L->size)
{
printf("元素序号越界！");
exit(1);
}
return L->list[pos-1]; /* 返回线性表中序号为Pos值的元素 */
}

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

/*值与X相等的元素，若查找成功则返回其位置，否则返回-1*/
int findList(struct List *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 updatePostList(struct List *L,int pos,ElemType x)
{
if(pos<1 || pos>L->size){
return 0 ;
}
L->list[pos-1]= x;
return 1 ;
}
/* 从线性表中L删除表头元素并返回它，若删除失败则停止程序运行 */
ElemType deleteFirstList(struct List *L)
{
ElemType temp;
int i ;
if(L->size == 0){
printf("线性表为空，不能进行删除操作！");
exit(1);
}
temp = L->list[0];
for(i = 0 ;i<L->size;i++)
L->list[i-1] = L->list[i];
L->size--;
return temp;
}
/* 线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行 */
ElemType deleteLastList(struct List *L)
{
if(L->size==0){
printf("线性表为空，不能进行删除操作！");
exit(1);
}
L->size--;
/* 返回原来表尾的值 */
return L->list[L->size];
}
/* 从线性表L中删除第pos个元素并返回它，若删除失则停止程序运行 */
ElemType deletePostList(struct List *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当前的长度，若L 为空则返回0 */
int sizeList(struct List *L)
{
return L->size ;
}
/* 是不是一个空列表 */
int EmptyList(struct List *L)
{
if(L->size==0){
return 1;
}
else{
return 0 ;
}
}

/* 清除线性表L中的所有元素，释放存储空间，使之成为一个空表 */
void clearList(struct List *L)
{
if(L->list!=NULL){
free(L->list);
L->list=0;
L->size = L->MaxSize = 0 ;

}
return ;
}

main()
{
int a[10]={2,4,6,8,10,12,14,16,18,20};
struct List L;
int i ;
initList(&L,5);
for(i = 0 ;i<10;i++)
{
insertLastList(&L,a[i]);
}
/* 在当前下标下存入该值 */
insertPostList(&L,11,48);
/* 在当前下标下输入该值 */
insertPostList(&L,3,25);
/* 按下标获得当前下标的值 */
printf("GetElem=%d\n",GetElem(&L,11));
/* 输出当前列表中的所有数据 */
traverseList(&L);
/* 查询与 当前指标的值 */
printf("%d\n",findList(&L,8));
/* 在当前指标下修改值 */
updatePostList(&L, 3, 20);
/* 批指标来获得值 */
printf("%d\n",GetElem(&L,3));
/* 从线性表L中删除头元素并返回它，若删除失败则停止程序运行 */
/* deleteFirstList(&L); */
/* 再删除表头 */
/* deleteFirstList(&L); */
/* traverseList(&L); */
/* 删除最后表头的值 */
/* deleteLastList(&L); */
/* deleteLastList(&L); */
/* 指定删除下标进行删除 */
printf("%d\n",deletePostList(&L,5));

printf("%d\n ", sizeList(&L));
printf("%d\n", EmptyList(&L));

traverseList(&L);
/* 清除线性列表 */
clearList(&L);
/* 清除了没有值了 */
traverseList(&L);
}