线性链表的基本操作
关于线性链表的基本操作, 包括链表的建立、插入、删除、显示等基本功能 #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0
#define OVERFLOW -2 typedef int Status; typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next;
}*LinkList;
Status ListEmpty(LinkList L) { //判断链表L 是否为空 if(L->next) { return ERROR; } else { return TRUE; } }
Status Listlength(LinkList L) { //求链表L 的长度 int i=1; LinkList p=L->next; //p指向第一个结点 while(p) //没到表尾 { i++; p=p->next; } return i; }
Status CreateLinkList(LinkList &L,int n) { //输入n 个元素的值, 建立带表头结点的单链表L.
LinkList p,q; int firstdata,nextdata; L=(LinkList)malloc(sizeof(LNode)); printf("请输入数据:\n"); scanf("%d",&firstdata); L->data=firstdata; p=L; for(int i=1;idata=nextdata; p->next=q; p=q; } p->next=NULL; printf("创建成功!\n"); return OK; }
Status InsertLinkList(LinkList L, int x, int y) { //在表L 中值为x 的节点前面插入一个值为y 的节点。 LinkList neW, p, q; neW = (LinkList )malloc(sizeof(LNode)); neW->data = y; neW->next = NULL; if ( L == NULL ) L = neW;
else if ( L->data == x ) { neW->next = L; L = neW; } else { q = L; p = L->next; while ((p->data != x) && (p != NULL)) { q = p; p = p->next; }
if (p->data == x) { neW->next = p; q->next = neW; } else q->next = neW; }
return OK; }
Status DeleteLinkList(LinkList L, int x) { //删除表L 中值为x 的节点 LinkList p, q, s; int temp; s = NULL; if ( L == NULL ) { printf("The list has no node.\n"); return ERROR; } else if ( L->data == x ) { s = L; L = s->next; } else { q = L; p = q->next; while ((p->data != x) && p != NULL) { q = p; p = p->next; return ERROR; } if (p->data == x) { q->next = p->next; s = p; } else if(p->data!= x) {
printf("The linklist has no this node.\n"); return ERROR; } } if ( s ) { temp = s->data; free(s); return (temp); } }
void PrintLinkList(LinkList L) { //显示出链表的全部元素 if (ListEmpty(L)) {
printf("链表已空,不能显示\n"); } else { LinkList p=L; while(p>0) { printf("%d \n",p->data); p=p->next; } } }
int main() {
int flag; int val,i;
LinkList L; int n=5;
printf("链表操作\n"); do {
printf("\t1)创建链表;\n\t"); printf("2)插入链表;\n\t"); printf("3)删除链表;\n\t");
printf("4)显示链表所有元素;\n\t");
printf("0)退出;\n\t"); printf("请选择操作:");
if (0 != scanf("%d", &flag)) //检测输入是否合法,防止接收到非法输入时的误操作
{
switch (flag) {
否合法
合法
\n"); 合法
case 1: case 2: case 3: printf("请创建一个长度为5的链表\n"); if(!CreateLinkList(L,n)) { printf("内存不足!\n"); break; }
break; printf("请输入要插入的值(int):\n"); if ( 0 == scanf("%d", &val) ) //检测输入是{
printf("错误,请重新输入!\n"); break; } printf("请输入插入的链表的位置(int):\n"); if ( 0 == scanf("%d", &i) ) //检测输入是否{
printf("错误,请重新输入!\n"); break; }
else if ( InsertLinkList(L,i, val))
printf("插入后队列的元素是:\n"); PrintLinkList(L); break; printf("请输入要删除链表的元素的值(int):if ( 0 == scanf("%d", &i) ) //检测输入是否
{
printf("错误,请重新输入!\n"); break; } if(DeleteLinkList(L,i)) { printf("删除成功!\n");
} else {
} }while(0 != flag); return 0; }
printf("删除后链表的元素是:\n"); PrintLinkList(L); break; } else if(DeleteLinkList(L,i)==0)
printf("删除失败,空链表!\n"); break; case 4: printf("链表的长度为:%d\n",Listlength( L)); printf("链表的所有元素为:\n"); PrintLinkList(L); break;
default:
if (0 != flag)
printf("错误,请重新输入!\n"); break; } printf("错误,请重新输入!\n");