不带头结点的单链表
程序员文章站
2024-03-21 13:23:04
...
#include<cstdio>
#include<cstdbool>
#include<cstdlib>
#define OK 1
#define ERROR 0
typedef char Elemtype;
typedef struct Node {
Elemtype data;
struct Node *next;
}Node, *LinkList;
//初始化
void InitList(LinkList *L)
{
}
//头插法
void CreateFromHead(LinkList *L)
{
Node *s;
printf("Creating List From Head:\n");
char ch = getchar();
bool isEmpty = true;
while (ch != '$') {
s = (Node*)malloc(sizeof(Node));
s->data = ch;
s->next = *L;
*L = s;
if (isEmpty) {
(*L)->next = NULL;
isEmpty = false;
}
ch = getchar();
}
}
//尾插法
void CreateFromTail(LinkList *L)
{
Node *s, *rear= NULL;
printf("Creating List From Tail:\n");
char ch = getchar();
while (ch != '$')
{
s = (Node*)malloc(sizeof(Node));
s->data = ch;
if (*L == NULL) {
*L = s;
rear = s;
}
else {
rear->next = s;
rear = s;
}
ch = getchar();
}
rear->next = NULL;
}
//遍历链表元素然后输出
void Display(LinkList L) {
Node *p = L;
printf("The link list is:\n");
while (p) {
printf("%c", p->data);
p = p->next;
}
printf("\n");
}
//获取表长
int GetListLength(LinkList L)
{
int count = 0;
Node *p = L;
while (p) {
count++;
p = p->next;
}
return count;
}
//插入元素
int InsertList(LinkList *L, int i, Elemtype e)
{
Node *pre = *L, *s;
if (i <= 0) return ERROR;
int count = 0;
if (i == 1) {
s = (Node*)malloc(sizeof(Node));
s->data = e;
s->next = *L;
*L = s;
return OK;
}
while (pre) {
count++;
if (count < i - 1)
pre = pre->next;
else
break;
}
if (pre == NULL) {
printf("插入的位置不合理");
exit(1);
}
s = (Node*)malloc(sizeof(Node));
s->data = e;
s->next = pre->next;
pre->next = s;
return OK;
}
// 删除元素
int DelList(LinkList *L, int i, Elemtype *e)
{
if (*L == NULL) {
printf("空表无法删除");
exit(1);
}
if (i <= 0) return ERROR;
if (i == 1) {
Node *temp = *L;
*e = (*L)->data;//别忘了带回返回值
*L = (*L)->next;
free(temp);
return OK;
}
Node *pre = *L;
int count = 0;
while (pre->next) {
count++;
if (count < i - 1)
pre = pre->next;
else
break;
}
if (pre->next == NULL) {
printf("插入的位置不合理");
exit(1);
}
Node *r = pre->next;
*e = r->data;
pre->next = r->next;
free(r);
return OK;
}
//合并两个非递减链表至一个大的非递减列表,不借助新的辅助空间
LinkList MergeLinkList(LinkList La, LinkList Lb)
{
LinkList Lc = NULL;
Node *pa = La, *pb = Lb, *pc=Lc;
while (pa && pb) {
if (pa->data <= pb->data) {
if (pc == NULL) {
Lc = pa;
pc = pa;
}
else {
pc->next = pa;
pc = pa;
}
pa = pa->next;
}
else {
if (pc == NULL) {
Lc = pb;
pc = pb;
}
else {
pc->next = pb;
pc = pb;
}
pb = pb->next;
}
}
if (pa)
pc->next = pa;
if(pb)
pc->next = pb;
return Lc;
}
//合并两个非递减链表至一个大的非递增列表,不借助新的辅助空间
LinkList MergeLinkList2(LinkList La, LinkList Lb)
{
LinkList Lc=NULL;
Node *pa = La, *pb = Lb, *temp;
while (pa && pb) {
if (pa->data <= pb->data) {
temp = pa->next;
if (Lc == NULL) {
Lc = pa;
pa->next = NULL;
}
else {
pa->next = Lc;
Lc = pa;
}
pa = temp;
}
else {
temp = pb->next;
if (Lc == NULL) {
Lc = pb;
pb->next = NULL;
}
else {
pb->next = Lc;
Lc = pb;
}
pb = temp;
}
}
while (pa) {
temp = pa->next;
pa->next = Lc;
Lc = pa;
pa = temp;
}
while (pb) {
temp = pb->next;
pb->next = Lc;
Lc = pb;
pb = temp;
}
return Lc;
}
//编写递归算法,删除不带头结点的单链表L中所有值为x的结点
void DelXInList(LinkList *L, Elemtype x, Node **firstPre)
{
if (*L == NULL) return;
Node *temp;
if ((*L)->data == x) {
if (*firstPre != NULL) {
temp = *L;//一定要在下一步之前去保存*L的值,因为下一步的(*firstPre)->next其实就是L,所以如果free(*L), 释放了错误的结点空间
(*firstPre)->next = (*L)->next;
free(temp);
*L = (*firstPre)->next;
}
else {
temp = (*L)->next;
free(*L);
*L = temp;
}
DelXInList(L, x, firstPre);
}
else {
*firstPre = *L;
DelXInList(&((*L)->next), x, firstPre);
}
}
LinkList modifiedHead = NULL;
//编写递归算法,删除不带头结点的单链表L中所有值为x的结点
void DelXInList2(LinkList L, Elemtype x, Node **firstPre)
{
if (L != NULL) {
Node *temp;
if (L->data == x) {
if (*firstPre != NULL) {
(*firstPre)->next = L->next;
free(L);
L = (*firstPre)->next;
}
else {
temp = L->next;
free(L);
L = temp;
modifiedHead = L;
}
DelXInList2(L, x, firstPre);
}
else {
*firstPre = L;
DelXInList2(L->next, x, firstPre);
}
}
}
int main()
{
LinkList la=NULL, lb=NULL;
CreateFromHead(&la);// fed$
getchar();
CreateFromTail(&lb);//abc$
Display(la);
Display(lb);
//LinkList lc = MergeLinkList(la,lb);
//Display(lc);
LinkList ld = MergeLinkList2(la, lb);
Display(ld);
InsertList(&ld, 0, 'H');
InsertList(&ld, 1, 'H');
Display(ld);
InsertList(&ld, 8, '0' );
Display(ld);
char ch;
DelList(&ld, 1, &ch);
Display(ld);
printf("The deleted is %c",ch );
//注:两个合并操作不能同时进行,不然就会干扰,因为这里的合并都利用了原有的空间,所以链表结构发生了变化
//用于验证函数删除所有值为X的结点
LinkList le = NULL;
CreateFromTail(&le); // edbbcamtccbciok$
Node *firstPre = NULL;
Display(le);
DelXInList(&le, 'c', &firstPre);
Display(le);
firstPre = NULL;
DelXInList2(le, 'b', &firstPre);
if(modifiedHead)
le = modifiedHead;
Display(le);
return 0;
}
上一篇: 宏和函数的优缺点