实验一、单链表的插入和删除
一、目的
了解和掌握线性表的逻辑结构和链式存储结构,掌握单链表的基
本算法及相关的时间性能分析。
」|, 「、-
二、要求:
建立一个数据域定义为字符串的单链表,在链表中不允许有重复的字符串;根据输入的字符串,先找到相应的结点,后删除之。
三、程序源代码
#in clude"stdio.h"
#i nclude"stri ng.h" #i nclude"stdlib.h" #i nclude"ctype.h" typedef
struct node
{
char data[10];
struct node *n ext; }ListNode;
typedef ListNode *
Lin kList; //
Lin kList CreatListR1();
//
//
//
自定义
//
定义结点
结点的数据域为字符串
结点的指针域
Lin kList 单链表类型
函数,用尾插入法建立
带头结点的单链表
void DeleteList(); // 函数,删除指定值的结点 void printlist(); // 函数,打印链表中
的所有值 void DeleteAll(); // 函数,删除所有结点, 释放内存 //==========主函数 ============== void main()
{
用尾插入法建立单链表,返回头指针 遍历链表输出其值
输入“ y ”或“n ”去选择是否
删除结点
scanf("%s",num);
if(strcmp(num,"y")==0 || strcmp(num,"Y")==0){ printf("Please input
Delete_data:");
scanf("%s",ch);
// 输入要删除的字符串
DeleteList(head,ch); printlist(head);
char ch[10],num[10]; LinkList head; head=CreatListR1(); // printlist(head); // printf(" Delete node (y/n):");//
DeleteAll(head); //
}
删除所有结点,释放内存
// 用尾插入法建立带头结点的单链表
LinkList CreatListR1(void)
{
char ch[10];
LinkList head=(LinkList)malloc(sizeof(ListNode)); // 生成头结点
八\、
ListNode *s,*r,*pp;
r=head;
r->next=NULL;
printf("Input # to end "); // 输入“ #”代表输入结束
printf("Please input Node_data:");
scanf("%s",ch); // 输入各结点的字符串while(strcmp(ch,"#")!=0) { pp=LocateNode(head,ch); // 按值查找结点,返回结点指针if(pp==NULL) { // 没有重复的字符串,插入到链表中s=(ListNode
*)malloc(sizeof(ListNode));
strcpy(s->data,ch);
r->next=s;
r=s;
r->next=NULL;
printf("Input # to end ");
printf("Please input Node_data:");
scanf("%s",ch);
}
return head; // 返回头指针
}
//==========按值查找结点,找到则返回该结点的位置,否则返回
NULL==========
ListNode *LocateNode(LinkList head, char *key)
{
ListNode *p=head->next; // 从开始结点比较
while(p&&strcmp(p->data,key)!=O ) // 直到p 为NULL或p-> data 为key 止
p=p->next; // 扫描下一个结点
return p; // 若p=NULL则查找失败,否则p指向找到的值
key 的结点
}
//==========删除带头结点的单链表中的指定结点=======
void DeleteList(LinkList head,char *key)
{
ListNode *p,*r,*q=head;
p=LocateNode(head,key); // 按key 值查找结点的
printf("position error");
exit(0);
}
while(q->next!=p) //p 为要删除的结点,q 为p 的前结点q=q->next; r=q->next;
q->next=r->next;
free(r); // 释放结点
}
//=========== 打印链表======= void printlist(LinkList head)
{
ListNode *p=head->next; // 从开始结点打印
while(p){
printf("%s, ",p->data);
p=p->next;
}
printf("\n");
}
//==========删除所有结点,释放空间=========== void DeleteAll(LinkList head)