单链表的基本操作【超全】
实验二 链表的基本操作
一、实验目的
1、掌握链表的建立、插入元素、删除表中某元素的算法。
2、对线链表相应算法的时间复杂度进行分析。
二、实验要求
1．实验前做好充分准备，包括复习第二章所学内容，事先预习好本次实验内容。
2．实验时记录实验结果，按要求完成各题。
3．实验结束后，给出实验总结与分析并及时给出本次实验的实验报告。
三、实验内容
1.完成并实现如下链表的基本操作。要求：编写测试函数运行程序，给出结果每个基本操作的运行截图。
#include
#include
#include
typedef int ElemType; //定义类型
typedef struct LNode //定义结点
{
ElemType data; //数据域
struct LNode *next; //指向后继结点的指针域
}LNode,*PNode; //PNode为节点类型指针
typedef struct LinkList //定义链表
{
PNode first; //头指针
PNode last; //尾指针
int list_size; //链表中有效元素个数
}LinkList;
要求：完成并实现如下单链表的基本操作
/基本操作/
void InitLinkList(LinkList *list);//初始化链表
理解代码
LNode *_buyNode(ElemType Item);//新增结点
理解代码
void push_front(LinkList *list,ElemType x);//向链表中头插结点（5分）
代码：
LinkList* push_front(LinkList* list, ElemType x)
{ if (list == NULL) {
printf("头插传入参数有误");
return list;
}
LinkList* s = (LinkList*)malloc(sizeof(list));
s->data=x;
s->next = list->next;
list->next = s;
return list;
}
截图：
void push_back(LinkList *list,ElemType x);//向链表中尾插结点（5分）
代码：//尾插
LinkList* push_back(LinkList* list, ElemType x)
{
if (list == NULL) {
printf("尾插传入参数有误");
return list;
}
LinkList* r ;
r = list;
while (r->next!=NULL) {//让尾指针指向尾部
r = r->next;
}
LinkList* s = (LinkList*)malloc(sizeof(list));
s->data = x;
s->next = NULL;
r->next = s;//尾结点r
r = s;//r指向新的尾结点
return list;
}
截图：
正在上传…重新上传取消
void showList(LinkList *list);//显示链表元素（10分）
代码：
void showList(LinkList* list) {
LinkList* temp = list;//将temp指针重新指向头结点
//只要temp指针指向的结点的next不是Null，就执行输出语句。
while (temp->next) {
temp = temp->next;
printf("%d ", temp->data);
}
printf("\n");
}截图：
正在上传…重新上传取消
void pop_back(LinkList *list);//尾部删除结点（10分）
代码：
LinkList* pop_back(LinkList* list)
{
if (list == NULL) {
printf("尾删传入参数有误");
return list;
}
LinkList* r= list;//尾结点
LinkList* q=NULL;//指向尾结点前一结点
while (r->next != NULL) {//让尾指针指向尾部
q = r;
r = r->next;
}
q->next = NULL;
return list;
}
截图：
正在上传…重新上传取消
void pop_front(LinkList *list);//头部删除节点（10分）
代码：
//头删
LinkList* pop_front(LinkList* list)
{
if (list == NULL) {
printf("头删传入参数有误");
return list;
}
LinkList* r = NULL;//被删除结点指针
LinkList* q = list;
r = q->next;
q->next = r->next;
free(r);
return list;
}
截图：
正在上传…重新上传取消
int length_list(LinkList *list);//返回链表长度（10分）
代码：
int length_list(LinkList* list){
if (list == NULL) {
printf("长度传入参数有误");
return 0;
}
LinkList* p=list->next;//指向第一个结点
int i = 0;
while (p) {
i++;
p = p->next;
}
return i;
}
截图：
正在上传…重新上传取消
void insertLinklist_pos(LinkList *list,int pos,ElemType key);//按照pos指定的位置插入元素（10分）
代码：
LinkList* insertLinklist_pos(LinkList* list, int pos, ElemType key) {
LinkList* temp = list;//创建临时结点temp
LinkList* c = NULL;
int i = 0;
//首先找到要插入位置的上一个结点
for (i = 1; i < pos; i++) {
if (temp == NULL) {
printf("插入位置无效\n");
return list;
}
temp = temp->next;
}
//创建插入结点c
c = (LinkList*)malloc(sizeof(LinkList));
c->data = key;
//向链表中插入结点
c->next = temp->next;
temp->next = c;
return list;
}
截图：
正在上传…重新上传取消
void delete_LinkList_val(LinkList *list,ElemType x);//删除第一个值为x的元素（10分）
代码：
LinkList* delete_LinkList_val(LinkList* list, int x) {
LinkList* temp = list;
LinkList* del = NULL;
int i = 0;
//遍历到被删除结点的上一个结点
while (temp) {
if (temp->data == x)//temp当前指向的就是要删除的那个结点
break;
del = temp;//要删除的前一结点
temp = temp->next;
}
del->next = temp->next;//跳过值为x的结点
free(temp);//手动释放该结点，防止内存泄漏
return list;
}
截图：
正在上传…重新上传取消
void sortLinkList(LinkList *list); //排序
理解代码
void reverseLinkList(LinkList *list);//逆置链表元素
理解代码
LinkList* reverseLinkList(LinkList* list) {
list = list->next;
LinkList* temp; // 保存cur的下一个节点
LinkList* cur = list;
LinkList* pre = NULL;
while (cur) {
temp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next
cur->next = pre; // 翻转操作
// 更新pre 和 cur指针
pre = cur;
cur = temp;
}
return pre;
}
运行:
正在上传…重新上传取消
int findval_val(LinkList *list,ElemType key);//查找链表中首个值为key的元素位置（10分）
代码：
int findval_val(LinkList* list, ElemType key) {
LinkList* p = list;
p = list->next;
int j = 1;
while (p && p->data != key) {
p = p->next;
j++;
}
if (p) return j;
else return 0;
}
截图：
正在上传…重新上传取消
int countX(LinkList *list,ElemType x) 统计大于某个值的节点个数（10分）
代码：
int countX(LinkList* list, ElemType x) {
LinkList* p = list;
p = list->next;
int count = 0;
while (p ) {
if (p->data>x) {
count++;
}
p = p->next;
}
return count;
}
截图：
正在上传…重新上传取消
void clearLinkList(LinkList *list);//清空单链表
理解代码
void destroyLinkList(LinkList *list);//销毁单链表
理解代码
2.利用单链表结构实现单链表的基本应用
（1）单链表的拆分：拆分单链表l1，使得拆分后的单链表l1存奇数位置元素，l2逆序存偶数位置元素。例如：拆分前l1：1->2->3->4->5->6->7
拆分后：l1：1->3->5->7；
l2：6->4->2 （5分）
代码：
#include
#include
typedef int ElemType;
typedef struct Link {
ElemType data;
struct Link* next;
}LinkList;
//初始化
LinkList* initLink() {
LinkList* list = (LinkList*)malloc(sizeof(LinkList));//创建一个头结点
LinkList* temp = list;//声明一个指针指向头结点，用于遍历链表
int i = 0;
//生成链表
for (i = 1; i < 8; i++) {
LinkList* a = (LinkList*)malloc(sizeof(LinkList));
a->data = i;
a->next = NULL;
temp->next = a;
temp = temp->next;
}
return list;
}
//正序输出奇数
void jdisplay(LinkList* list) {
LinkList* temp = list;//将temp指针重新指向头结点
//只要temp指针指向的结点的next不是Null，就执行输出语句。
while (temp->next) {
temp = temp->next;
if(temp->data%2!=0) printf("%d ", temp->data);
}
printf("\n");
}
//逆置链表元素
LinkList* reverseLinkList(LinkList* list) {
list = list->next;
LinkList* temp; // 保存cur的下一个节点
LinkList* cur = list;
LinkList* pre = NULL;
while (cur) {
temp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next
cur->next = pre; // 翻转操作
// 更新pre 和 cur指针
pre = cur;
cur = temp;
}
return pre;
}
//倒叙输出偶数
void oredisplay(LinkList* list) {
LinkList* temp = list;//将temp指针重新指向头结点
//只要temp指针指向的结点的next不是Null，就执行输出语句。
while (temp) {
if(temp->data%2==0) printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int mian(){
LinkList* list = NULL;
int address;
printf("初始化链表为：\n");
list = initLink();
display(list);
printf("拆分后链表:\n");
jdisplay(list);
LinkList* pre = reverseLinkList(list);
oredisplay(pre);}
截图：
正在上传…重新上传取消
（2）链表的合并：将有序单链表l1、l2合并为l3后仍有序。（5分）
代码：#include
#include
typedef int ElemType;
typedef struct Link {
ElemType data;
struct Link* next;
}LinkList;
LinkList* initLink() {
LinkList* list = (LinkList*)malloc(sizeof(LinkList));//创建一个头结点
LinkList* temp = list;//声明一个指针指向头结点，用于遍历链表
int i = 0;
//生成链表
for (i = 1; i < 8; i++) {
LinkList* a = (LinkList*)malloc(sizeof(LinkList));
a->data = i;
a->next = NULL;
temp->next = a;
temp = temp->next;
}
return list;
}
void display(LinkList* list) {
LinkList* temp = list;//将temp指针重新指向头结点
//只要temp指针指向的结点的next不是Null，就执行输出语句。
while (temp->next) {
temp = temp->next;
printf("%d ", temp->data);
}
printf("\n");
}
//合并
void MergeList(LinkList* lista, LinkList* listb, LinkList* listc) {
LinkList* pa = NULL;
LinkList* pb = NULL;
LinkList* pc = NULL;
pa = lista->next;
pb = listb->next;
pc = listc = lista;//用La的头节点作为Lc的头节点
while (pa && pb) {
if (pa->data <= pb->data) {
pc->next = pa;
pc = pa;
pa = pa->next;
}
else {
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb;//插入剩余段
free(listb);
}
int main() {
LinkList* lista = NULL;
LinkList* listb = NULL;
LinkList* listc = NULL;
printf("初始化链表为：\n");
lista = initLink();
printf("lista链表的值：\n");
display(lista);
listb = initLink();
printf("listb链表的值：\n");
display(listb);
MergeList(lista, listb, listc);
printf("listc合并链表的值：\n");
display(lista);
}
截图：
正在上传…重新上传取消
四、实验小结
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！