前言
熟练掌握带头节点的单链表的相关操作，
头文件
#include <stdio.h>
#include <stdlib.h>
/**************************************/
/* 链表实现的头文件，文件名slnklist2.h */
/**************************************/
typedef int datatype;
typedef struct link_node {
datatype info;
struct link_node *next;
}node;
typedef node *linklist;
/******************************************/
/*函数名称：creatbystack() */
/*函数功能：头插法建立带头结点的单链表 */
/******************************************/
linklist creatbystack()
{
linklist head, s;
datatype x;
head = (linklist)malloc(sizeof(node));
head->next = NULL;
printf("请输入整数序列（空格分开，以0结束）:\n");
scanf("%d", &x);
while (x != 0)
{
s = (linklist)malloc(sizeof(node));
s->info = x;
s->next = head->next;
head->next = s;
scanf("%d", &x);
}
return head;
}
/***************************************/
/*函数名称：creatbyqueue() */
/*函数功能：尾插法建立带头结点的单链表 */
/***************************************/
linklist creatbyqueue()
{
linklist head, r, s;
datatype x;
head = r = (linklist)malloc(sizeof(node));
head->next = NULL;
printf("请输入整数序列（空格分开，以0结束）:\n");
scanf("%d", &x);
while (x != 0)
{
s = (linklist)malloc(sizeof(node));
s->info = x;
r->next = s;
r = s;
scanf("%d", &x);
}
r->next = NULL;
return head;
}
/**********************************/
/*函数名称：print() */
/*函数功能：输出带头结点的单链表 */
/**********************************/
void print(linklist head)
{
linklist p;
int i = 0;
p = head->next;
printf("List is:\n");
while (p)
{
printf("%7d", p->info);
i++;
if (i % 10 == 0) printf("\n");
p = p->next;
}
printf("\n");
}
/******************************************/
/*函数名称：creatLink() */
/*函数功能：从文件中读入n个数据构成单链表 */
/******************************************/
linklist creatLink(char *f, int n)
{
FILE *fp;
int i;
linklist s, head, r;
head = r = (linklist)malloc(sizeof(node));
head->next = NULL;
fp = fopen(f, "r");
if (fp == NULL)
return head;
else
{
for (i = 0; i<n; i++)
{
s = (linklist)malloc(sizeof(node));
fscanf(fp, "%d", &(s->info));
r->next = s;
r = s;
}
r->next = NULL;
fclose(fp);
return head;
}
}
/*
函数名称：writetofile
函数功能：将链表内容存入文件f
*/
void writetofile(linklist head, char *f)
{
FILE *fp;
linklist p;
int i = 0;
fp = fopen(f, "w");
if (fp != NULL)
{
p = head->next;
fprintf(fp, "%s", "List is:\n");
while (p)
{
fprintf(fp, "%7d", p->info);
i++;
if (i % 10 == 0) fprintf(fp, "%c", '\n');
p = p->next;
}
fprintf(fp, "%c", '\n');
fclose(fp);
}
else printf("创建文件失败!");
}
/**********************************/
/*函数名称：delList() */
/*函数功能：释放带头结点的单链表 */
/**********************************/
void delList(linklist head)
{
linklist p = head;
while (p)
{
head = p->next;
free(p);
p = head;
}
}
1.已知线性表存储在带头结点的单链表head中，请设计算法函数void sort(linklist head)，将head中的结点按结点值升序排列。
#include"slinklist2.h"
/*
已知线性表存储在带头结点的单链表head中，请设计算法函数void sort(linklist head)，将head中的结点按结点值升序排列。
*/
/*请将本函数补充完整，并进行测试*/
#define N 50
void sort(linklist head)
{
int number[N];
int i = 0;
linklist p;
p = head->next;
while (p)
{
number[i++] = p->info;
p = p->next;
}
//冒泡排序
for (int j = 0; j < i-1; j++)
{
for(int k=j+1;k<i;k++)
if (number[j] > number[k])
{
int temp = number[k];
number[k] = number[j];
number[j] = temp;
}
}
p = head->next;
int m = 0;
while (p)
{
p->info = number[m++];
p = p->next;
}
}
int main()
{
linklist head;
head = creatbyqueue(); /*尾插法建立带头结点的单链表*/
print(head); /*输出单链表head*/
sort(head); /*排序*/
print(head);
delList(head);
system("pause");
return 0;
}
2.已知两个带头结点的单链表L1和L2中的结点值均已按升序排序，设计算法函数linklist mergeAscend (linklist L1,linklist L2)将L1和L2合并成一个升序的带头结单链表作为函数的返回结果；设计算法函数linklist mergeDescend (linklist L1,linklist L2)将L1和L2合并成一个降序的带头结单链表作为函数的返回结果；并设计main()函数进行测试。
#include"slinklist2.h"
/*请将本函数补充完整，并进行测试*/
linklist mergeAscend(linklist L1, linklist L2)
{
linklist L3, p1, p2, p3;//p1,p2分别为L1,L2上链
p1 = L1->next;
p2 = L2->next;
L3 = p3 = (linklist)malloc(sizeof(node));
while (p1&&p2)
{
if (p1->info < p2->info)
{
p3->next = p1;
p3 = p3->next;
p1 = p1->next;
}
else
{
p3->next = p2;
p3 = p3->next;
p2 = p2->next;
}
}
//因为是升序，故直接链接到还有剩余未比较节点的链表
if (p1) p3->next = p1;
if (p2) p3->next = p2;
free(L1);
free(L2);
return L3;
}
linklist mergeDescend(linklist L1, linklist L2)//降序麻烦点
{
linklist L3, p1, p2, p3,pre;
p1 = L1->next;
p2 = L2->next;
L3 =p3= (linklist)malloc(sizeof(node));
/*这里我是先把两个升序链表倒置，然后再利用*/
L1->next = NULL;
L2->next = NULL;
while (p1)
{
pre = p1;
p1 = p1->next;
pre->next = L1->next;
L1->next = pre;
}
while (p2)
{
pre = p2;
p2 = p2->next;
pre->next = L2->next;
L2->next = pre;
}
//注意这里要重新上链，因为经过倒置后p1,p2==NULL
p1 = L1->next;
p2 = L2->next;
while (p1&&p2)
{
if (p1->info > p2->info)
{
p3->next = p1;
p3 = p3->next;
p1 = p1->next;
}
else
{
p3->next = p2;
p3 = p3->next;
p2 = p2->next;
}
}
if (p1) p3->next = p1;
if (p2) p3->next = p2;
free(L1);
free(L2);
return L3;
}
int main()
{
linklist h1, h2, h3;
h1 = creatbyqueue(); /*尾插法建立单链表,请输入升序序列*/
h2 = creatbyqueue();
print(h1);
print(h2);
// h3= mergeAscend(h1, h2);/*升序合并到h3*/
h3 = mergeDescend(h1, h2); /*降序合并请调用h3=mergeDescend(h1,h2); */
print(h3);
delList(h3);
system("pause");
return 0;
}
3.设计一个算法linklist interSection(linklist L1,linklist L2)，求两个单链表表示的集合L1和L2的交集，并将结果用一个新的带头结点的单链表保存并返回表头地址。
#include"slinklist2.h"
/*请将本函数补充完整，并进行测试*/
linklist interSection(linklist L1, linklist L2)
{
linklist L3, p1, p2, p3,temp;
p3 = (linklist)malloc(sizeof(node));
L3 = p3;
p1 = L1->next;
while (p1)
{
p2 = L2->next;
while(p2&&p1->info != p2->info)
p2 = p2->next;
if (p2)//匹配成功
{
temp = (linklist)malloc(sizeof(node));
temp->info = p1->info;
p3->next = temp;
p3 = p3->next;
}
p1 = p1->next;
}
p3->next = NULL;//注意末节点设空
return L3;
}
int main()
{
linklist h1, h2, h3;
h1 = creatbyqueue(); /*尾插法建立单链表,输入时请勿输入重复数据*/
h2 = creatbyqueue();
print(h1); /*输出单链表h1*/
print(h2);
h3 = interSection(h1, h2); /* 求h1和h2的交集*/
print(h3);
delList(h1);
delList(h2);
delList(h3);
system("pause");
return 0;
}
4.请编写一个算法函数void partion(linklist head)，将带头结点的单链表head中的所有值为奇数的结点调整到链表的前面，所有值为偶数的结点调整到链表的后面。
#include "slinklist2.h"
/*请将本函数补充完整，并进行测试*/
void partion(linklist head)
{
linklist p, pre;
p = head->next;//p上链
pre = head;//与p配套的前驱指针
while (p&&p->info%2==1)//是奇数就一直下滑
{
pre = p;
p = p->next;
}
while (p)//p指到偶数
{
while (p&&p->info % 2 == 0) {//是偶数就继续下滑
pre = p;
p = p->next;
}
if (p) {//遇到奇数，改变next域
pre->next = p->next;
p->next = head->next;
head->next = p;
p = pre->next;
}
}
}
int main()
{
linklist head;
head = creatbyqueue(); /*尾插法建立带头结点的单链表*/
print(head); /*输出单链表head*/
partion(head);
print(head);
delList(head);
system("pause");
return 0;
}
5.编写一个程序，用尽可能快的方法返回带头结点单链表中倒数第k个结点的地址，如果不存在，则返回NULL
#include "slinklist2.h"
/*请将本函数补充完整，并进行测试*/
linklist search(linklist head, int k)
{
//方法一
linklist p, pre;
int count = 0;
p = head->next;
pre = head;
head->next = NULL;
while (p) {//将链表转置
pre = p;
p = p->next;
pre->next = head->next;
head->next = pre;
}
//p重新上链
p = head->next;
while (p&&count != k){
count++;
pre = p;
p = p->next;
}
if (p){//有倒数第k个节点
return pre;
}
else{
return NULL;
}
/*
方法二
linklist pre, p;
int count = 0;
p = head->next;
while (p && count<k)
{
p = p->next;
count++;
}
if (count<k) return NULL;
pre = head->next;
while (p)
{
pre = pre->next;
p = p->next;
}
return pre;*/
}
int main()
{
int k;
linklist head, p;
head = creatbyqueue(); /*尾插法建立带头结点的单链表*/
print(head); /*输出单链表head*/
printf("k=");
scanf("%d", &k);
p = search(head, k);
if (p) printf("%d\n", p->info);
else
printf("Not Found!\n");
delList(head);
system("pause");
return 0;
}
后记
一花一世界，一叶一追寻；一曲一场叹，一生为一人。
京公网安备 11010502036488号