单链表的C语言编程问题

Question

二、实验内容 自行设计程序实现1．建立一个单链表。2．并在指定的位置完成插入、删除运算。3．并输出插入、删除结点后的单链表。 实验结果及分析

Answer 1

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>//建立一个结构体数据类型的结点，要求有next在链表中指向下一个结点
struct DATA
{
int data;
struct DATA *next; //指向下一个结点的指针
};//函数声明
struct DATA *insert(struct DATA *head, int val); //结点的插入操作
struct DATA *del(struct DATA *head, int val); //结点的删除操作
void print(struct DATA *head); //打印链表int main(int argc, char* argv[])
{
struct DATA *head = NULL;
int val; for (;;)
{
printf("输入数据建立链表(输入0结束):\n");
for (;;)
{
scanf("%d",&val);
if (0 == val)
{
break;
}
head = insert(head,val);
} printf("下面开始输出链表:\n");
print(head); printf("输入要删除的结点(输入0结束):\n");
for (;;)
{
scanf("%d",&val);
if (0 == val)
{
break;
}
head = del(head,val);
}
print(head);
} return 0;
}struct DATA *insert(struct DATA *head, int val)
{
struct DATA *p = NULL; //要插入的结点的指针
struct DATA *p1 = NULL; //该指针定义为比p更大的结点
struct DATA *p2 = NULL; //定义两个指针用于辅助结点插入，指针指向：p2->p1 //初始化要插入结点
p = (struct DATA *)malloc(sizeof(struct DATA));
if (NULL == p)
{
printf("分配内存失败!!");
return head;
}
p->data = val;
p->next = NULL; if (head == NULL)//如果链表为空，直接插入到链表头
{
head = p;
}
else //链表不为空
{
if (p->data < head->data) //按升序将结点插入链表，插入数据比头结点小，直接插入到表头
{
p->next = head; //p的下一个结点指针直接指向链表头结点
head = p; //头结点指向p
}
else //插入的数据比原链表中的数据更大或者相等
{
//依次从链表中找到比插入结点更大的结点p1，将p2的下一个结点的指针指向p，p的下一个结点的指针指向p1;
//即将p插入到p2和p1得中间，指针指向变为：p2->p->p1
for (p2 = head, p1 = head->next; p1 != NULL; p2 = p1, p1 = p1->next)
{
if (p->data < p1->data) //找到p1结点
{
//改变指针指向
p2->next = p;
p->next = p1;
break;
}
}
if (p1 == NULL)//不存在p1结点，说明p说链表中最大的结点，直接将表尾的结点的下一个接结点指针指向p
{
p2->next = p;
}
}
} //返回链表头指针
return head;
}struct DATA *del(struct DATA *head, int val)
{
struct DATA *p = NULL; //欲删除的结点
struct DATA *p2 = NULL; //要删除的结点的上一个结点，指针指向为：p2->p if (head->data == val) //如果要删除的是头结点
{
p = head; //p指向头结点，即记录头结点的指针
head = head->next; //将头结点指针指向它的下一个结点
free(p); //释放p所指向的内存
} p2 = head; //p2指向链表头
p = head->next; //p指向链表头的下一个结点，即：p2->p
while (p != NULL) //查找链表知道链表为空
{
if (p->data == val) //找到要删除的结点
{
p2->next = p->next; //原指针指向：p2->p, 假设p的下一个指针为X，现修改为：p2->X
free(p); //释放p结点指向的内存

//实现删除重复结点
p = p2->next; //p指向p2的下一个结点即X，即又形成：p2->p
continue; //继续查找
}
p2 = p; //p2指针指向p, p2指针移动到它的下一个结点
p = p->next; //p指针也移动到它的下一个结点
} return head; //返回表头，有可能为空
}void print(struct DATA *head)
{
struct DATA *p = NULL; //从头结点依次打印结点到链表为空
for (p = head;p != NULL; p = p->next)
{
printf("%d -> ",p->data);
} printf("NULL \n"); return;
}

Answer 2

#include <iostream>#include <stdio.h>
using namespace std; typedef struct student{
int data;
struct student *next;
}node; node *creat(void){ //建立单链表
node *head;
node *p1;
node *p2;
int x;
int flag=1; head = (node *)malloc(sizeof(node));
p1 = head;
while(flag){
printf("输入数据:\n");
scanf("%d",&x);
/*if(x!=0){
p1->data = x;
}else{
flag = 0;
}*/
p1->data = x;
if(x==0)
{
flag = 0;
break;
}
p2 = (node *)malloc(sizeof(node));
p1->next = p2;
p1 = p2;
}
// p1->data = 0;
p1->next = NULL;
return head;
} int lengthlist(node *head){ //测长
int length=0;
node *p; p = head;
while(p!=NULL){
length++;
p = p->next;
}
return length;
} node *sort(node *head){ //插入
node *p;
int i,j,n;
int temp;

if(head==NULL||head->next == NULL){
return head;
}
p = head;
n = lengthlist(head);
for(i = 1; i<n; ++i){
p = head;
for(j = 1; j<=n-i; j++){
if(p->data>p->next->data){
temp = p->data;
p->data = p->next->data;
p->next->data = temp;
}
p = p->next;
}
}
return head;
} node *del(node *head, int data){ //删除
node *p,*p1;
p = head;
if(p->data == data){
head = p->next;
free(p);
}else{
while(p!=NULL&&data!=p->data){
p1 = p;
p = p->next;
}
if(p->data == data){
p1->next = p->next;
free(p);
}else{
cout<<"找不到.";
}
}
return head;
} void printlist(node * head){ //打印
node *p;
p = head;
while(p!=NULL){
cout<<p->data<<" ";
p = p->next;
}
} int main(){
int length;
node *head;
head = creat();
length = lengthlist(head);
cout<<length<<endl;
printlist(head);
head = del(head,10);
cout<<'\n';
printlist(head);
insert(head, 2, 100);
cout<<endl;
printlist(head);
sort(head);
cout<<endl;
printlist(head);
head = reverse(head);
cout << endl;
printlist(head); free(head);
//head=NULL;
return 0;
}本回答被网友采纳

Answer 3

struct NODE
{
int num;
char *name;
NODE *next;
};class MyList
{
private:
NODE *head,*pRead,*pAdd;
int listSize;
public :
MyList();
~MyList(); void addNode(NODE* newNode);
void addNode(NODE* newNode,int n);
void delNode(NODE *delNode);
void printListSize();
void printList();

}; 这是我的链表类。里面实现添加和删除