对链表相关知识的整理
花了两周整理链表的相关知识
以一个主函数和多个函数的形式来呈现
/*链表合集*/
#include<iostream>
#include<cstdlib>
using namespace std;
typedef struct node{
int a;
struct node *next;
} Node;
//排序
void Sort(Node*head){
node *p, *s, *pt;
p = head;
s = p->next;
while (p->next != NULL){
while(s->next != NULL){
if(p->next > s->next){
pt->next = p->next;
p->next = s->next;
s->next = pt->next;
}
s = s->next;
}
p = p->next;
pt = s;
}
}
Node *add(Node*head,int num){//在表尾插入元素
Node *p = NULL, *pr = head;
p = (Node *)malloc(sizeof(Node));
if(p == NULL){
cout << "no enough memory to allocate";
}
if(head == NULL){
head = p;
}else{
while(pr->next != NULL){
pr = pr->next;
}
pr->next = p;
}
p->a = num;
p->next = NULL;
return head;
}
//打印链表
void show(Node*head){
Node *p = head;
while(p != NULL){
cout << p->a << " ";
p = p->next;
}
}
void del(Node*head){//释放申请的内存空间
Node *p = head, *pr = NULL;
while(p != NULL){
pr = p;
p = p->next;
free(pr);
}
}
//删除链表里某一个节点
Node* Delete(Node*head,int num){
Node *p = head, *pr = head;
//pr是目标元素前一个节点
if(head == NULL){
cout << "empty table";
return head;//空表退出
}
while(num != p->a && p->next != NULL){
//未找到且不是空表
pr = p;
p = p->next;//p直接指向当前节点的下一节点
}
if(num == p->a){//找到了待删除节点
if(p == head){
head = p->next;//直接让头指针指向待删除结点p的下一节点
}else{
pr->next = p->next;
//前一节点的指针域指向待删除结点的下一节点
}
free(p);
}else{//到表尾且没找到
cout << "not found";
}
return head;
}
//在链表里插入元素
Node* insert(Node*head,int num){
Node *pr = head, *p = head, *temp = NULL;
p = (Node *)malloc(sizeof(Node));
if(p == NULL){
cout << "no enough memory";
exit(0);
}
p->next = NULL;//待插入节点指针域为空指针
p->a = num;//待插入节点的数值域为num
if(head == NULL){
head = p;//若原链表为空表，待插入节点为头节点
}else{//若为非空
//若未找到待插入节点的位置且未找到表尾则继续找
while(pr->a < num && pr->next != NULL){
temp = pr;//temp保存当前节点的下一节点
pr = pr->next;//pr指向当前节点的下一节点
}
if(pr->a >= num){
if(pr == head){//若在头节点前插入新节点
p->next = head;
//将新节点的指针域指向原链表的头节点
head = p;//让head指向新节点
}else{//在链表中部插入新节点
//进行排序
pr = temp;
p->next = pr->next;
pr->next = p;
}
}else{//若在表尾插入新节点
pr->next = p;//让末节点的指针域指向新节点
}
}
return head;//返回插入新节点猴的链表头指针head的值
}
int main()
{
int num;
char ch;
struct node *head = NULL;
do{
cin >> num;
if(num >= 0){
head = add(head, num);
show(head);
}
if(num % 5 ==0){
cout << "continue?(y/n)";
cin >> ch;
if((ch == 'n') || (ch == 'N')){
break;
}
}//避免死循环
} while (num >= 0);
del(head);
}