Question

C语言中数据结构中的单向链表的问题；

1、设线性表采用带表头附加结点的单链表存储结构，请编写线性表抽象数据类型各基本操作的实现函数，并存放在头文件LinkList.h中（注：教材上为不带表头附加结点）。同时建立一个验证操作实现的主函数文件test5.cpp，编译并调试程序，直到正确运行。
⑴ 单向链表的存储结构可定义如下：
struct LNode { // 定义单链表节点类型
ElemType data; // 存放结点中的数据信息
LNode *next; // 指示下一个结点地址的指针
}
⑵ 线性表基本操作可包括如下一些：
① void InitList (LNode *&H) //初始化单链表
② void ClearList(LNode *&H) //清除单链表
③ int LengthList (LNode *H) //求单链表长度
④ bool EmptyList (LNode *H) //判断单链表是否为空表
⑤ ElemType GetList (LNode *H, int pos)
//取单链表第 pos 位置上的元素
⑥ void TraverseList(LNode *H) //遍历单链表
⑦ bool InsertList ( LNode *&H, ElemType item, int pos)
//向单链表插入一个元素
⑧ bool DeleteList ( LNode *&H, ElemType &item, int pos)
//从单链表中删除一个元素
⑶ 带表头附加结点的单链表初始化操作的实现可参考如下：
void InitList(LNode *&H)
{ //构造一个空的线性链表H，即为链表设置一个头结点，
//头结点的data数据域不赋任何值，头结点的指针域next则为空
H=(LNode *)malloc(sizeof(LNode)); // 产生头结点H
if (!H) exit(0); // 存储分配失败，退出系统
H->next=NULL; // 指针域为空
}

Answer 1

#include "stdlib.h"
#include "stdio.h"

//链表的类型定义
typedef struct node
{
int data; //值域
struct node *link; //指针域
}*PNode,*LinkList;
//typedef struct node *PNode;
//typedef struct node *LinkList;

//创建空链表
LinkList createNullist_link(void)
{
LinkList list=(LinkList)malloc(sizeof(struct node));//申请表头结点空间
if(list!=NULL) list->link=NULL;
else printf("Out of space!\n");//创建失败
return(list);
}

//判断空链表
int isNullist_linkq(LinkList list)
{
return(list->link==NULL);
}

//在单链表中求某元素的存储位置
PNode locate_link(LinkList list,int x)
{//在list 带有头结点的单链表中找第一个值为x的结点存储位置
PNode p;
if(list->link==NULL) return(NULL);
p=list->link;
while(p!=NULL && p->data!=x) p=p->link;
return(p);
}

// 单链表的插入
int insertPost_link(LinkList list,PNode p,int x)
{//在list 带有头结点的单链表中,p所指结点后面插入元素x
PNode q=(PNode )malloc(sizeof(struct node));
if(q==NULL)
{
printf("Out of space!!!\n");
return(0);
}
else
{
q->data=x;
q->link=p->link;
p->link=q;
return(1);
}
}

// 在单链表求p所指结点的前驱结点
PNode locatePre_link(LinkList list,PNode p)
{
PNode p1;
if(list->link==NULL) return(NULL);
while(p1!=NULL && p1->link!=p) p1=p1->link;
return(p1);
}

// 单链表的删除
int insertPost_link(LinkList list,int x)
{//在list 带有头结点的单链表中删除第一个值为x的结点
PNode p,q ;
p=list;
if(p->link==NULL) return(0);
while(p->link!=NULL && p->link->data!=x)
p=p->link;//找值为x的结点的前驱结点的存储位置
if(p->link==NULL) //没找到值为x的结点
{
printf("Not exist!\n");
return(0);
}
else
{
q=p->link;
p->link=q->link;
free(q);
return(1);
}
}

void main()
{
int i,x;
PNode p;
LinkList list1;
list1=createNullist_link();
if(list1!=NULL)
printf("创建空表成功！\n");
p=list1;
for(i=0;i<5;i++)
{
printf("请输入第 %d 个结点的值：",i+1);
scanf("%d",&x);
insertPost_link(list1,p,x);
p=p->link;
}
printf("\n");
p=list1->link;
while(p!=NULL)
{
if(p->link==NULL)
printf("%d",p->data);
else
printf("%d->",p->data);
p=p->link;
}
printf("\n");
printf("请输入删除结点的值：",i+1);
scanf("%d",&x);
insertPost_link(list1,x);
printf("\n");
p=list1->link;
while(p!=NULL)
{
if(p->link==NULL)
printf("%d",p->data);
else
printf("%d->",p->data);
p=p->link;
}

}

Answer 2

#include <stdio.h>
#include <windows.h>

typedef struct node
{
int num;
struct node *next;
}lnode;

lnode *creat()
{
lnode *head,*p,*q;
int n;

head=NULL;

printf("输入要创建的节点数\n");
scanf("%d",&n);
while(n)
{
p=(lnode *)malloc(sizeof(lnode));
printf("输入数据\n");
scanf("%d",&p->num);
if (head==NULL)
{
head=q=p;
}
else
{
q->next=p;
q=p;
}
n--;
}
q->next=NULL;
return head;
}

lnode *insert(lnode *head)
{
lnode *p,*q,*s;
int n;
char ch;

q=p=head;

printf("输入插入的位置\n");
scanf("%d",&n);
printf("请选择是插入在前还是在后(F or B)\n");
getchar();
ch=getchar();
if(ch=='F'||ch=='f')
{
s=(lnode *)malloc(sizeof(lnode));
printf("请输入数据\n");
scanf("%d",&s->num);
while(p&&--n)
{
q=p;
p=p->next;
}
if (q==p)
{
s->next=q;
return s;
}
else
{
q->next=s;
s->next=p;
return head;
}
}
else if (ch=='B'||ch=='b')
{
s=(lnode *)malloc(sizeof(lnode));
printf("请输入数据\n");
scanf("%d",&s->num);
while(p&&n--)
{
q=p;
p=p->next;
}
if (NULL==q->next)
{
q->next=s;
s->next=NULL;
return head;
}
else
{
q->next=s;
s->next=p;
return head;
}
}
else
{
printf("输入错误\n");
}

}
lnode *del(lnode *head)
{
lnode *p,*q;
int n;
int flag=0;

p=q=head;
printf("请输入删除的数据\n");
scanf("%d",&n);
while(p)
{

if (p->num==n)
{
flag=1;
if (head==p)
{
head=head->next;

}
else if(NULL==p->next)
{
q->next=NULL;

}
else
{
q->next=p->next;

}
}
q=p;
p=p->next;
}
if (flag==0)
{
printf("没有找到数据\n");
system("pause");
}
else
{
printf("删除成功\n");
system("pause");
}
return head;
}

lnode *sort(lnode *head)
{
lnode *t,*f,*min,*p_min,*s;
char ch;

f=NULL;

printf("请输入排序方式：升序(A/a),降序(D/d)\n");
getchar();
ch=getchar();
if (ch=='A'||ch=='a')
{
while(NULL!=head)
{
for (min=head,s=head;s->next!=NULL;s=s->next)
{
if (min->num>s->next->num)
{
p_min=s;
min=s->next;

}
}
if (NULL==f)
{
f=min;
t=min;
}
else
{
t->next=min;
t=min;
}
if (min==head)
{
head=head->next;
}
else
{
p_min->next=min->next;
}
}
if (f!=NULL)
{
t->next=NULL;
}
printf("排序完成\n");
system("pause");
head=f;
return f;
}
else if (ch=='D'||ch=='d')
{
while(NULL!=head)
{
for (min=head,s=head;s->next!=NULL;s=s->next)
{
if (min->num<s->next->num)
{
p_min=s;
min=s->next;

}
}
if (NULL==f)
{
f=min;
t=min;
}
else
{
t->next=min;
t=min;
}
if (min==head)
{
head=head->next;
}
else
{
p_min->next=min->next;
}
}
if (f!=NULL)
{
t->next=NULL;

}
printf("排序完成\n");
system("pause");
head=f;
return f;

}
}

void dispaly(lnode *head)
{
lnode *p;

p=head;

printf("\n");
while(p!=NULL)
{
printf("%d\t",p->num);
p=p->next;
}
}

int getoption()
{
int n;

printf("0 退出\n");
printf("1 创建链表\n");
printf("2 插入节点\n");
printf("3 删除节点\n");
printf("4 排序节点\n");
printf("5 显示链表\n");
printf("请选择操作\t");
scanf("%d",&n);
return n;
}

int main()
{
lnode *temp;
char ch;
int o;

do
{
system("cls");
o=getoption();
switch (o)
{
case 0:
exit(0);
break;
case 1 :
system("cls");
temp=creat();
break;
case 2:
system("cls");
temp=insert(temp);
break;
case 3:
system("cls");
temp=del(temp);
break;
case 4:
system("cls");
temp=sort(temp);
break;
case 5:
system("cls");
dispaly(temp);
system("pause");
break;

}
system("cls");
printf("按0退出,任意键继续\t");
ch=getchar();
if (ch=='0')
{
exit(0);
}
} while (ch!='0');
}

Answer 3

有什么问题？不会要别人帮你写复杂程序吧？

Answer 4

我也在学，加油啊