PPC的C/C++和人工智能学习笔记
每一篇学习笔记,都只是为了更好地掌握和理解

C语言基础(15-1)_链表练习

学完了动态内存分配,尝试做一个:没有头结点的单链表来练习一下。具体链表的操作,还是在数据结构课程里面详细表达。

 

代码和结果图如下:

/********************************************
Copyright(C) 2017,www.vsppc.com
FileName: 无头结点单链表.c
Author: ppc
Version:
Date: 2017-02-28
Description:
 0.创建链表:因为无头节点,所以创建链表就是 建立一个 空指针。
 1.获取第几个位置的元素
 int GetNode(const LPLIST const List,int pos,LPLIST e); //返回1成功0失败,pos位置1开始
 2.头插法,插入结点
 int InsertNodeHead(LPLIST *List, int data); //返回1成功,0失败
 3.尾插法,插入结点
 int InsertNodeTail(LPLIST *List, int data); //返回1成功,0失败
 4.插入指定位置
 int InsertNodePos(LPLIST *List,int data,int pos) //pos从1开始
 5.链表是否为空
 int IsEmptyList(LPLIST List)
 6.打印链表
 void PrintList(const LPLIST const List)
 7.查找链表元素
 int LocateNode(LPLIST List,LPLIST e) 返回值是元素的位置,0表示没找到,第1个是1
 //8.头删除
 // int DeleteHead(LPLIST *List)
 //9.尾删除
 // int DeleteTail(LPLIST *List)
 10.指定位置删除
 int DeletePos(LPLIST *List,int pos) //pos从1开始
 11.从小到大排序链表
 void SortList(LPLIST *List)
 12.删除整个链表
 void DeleteList(LPLIST *List)
 13.获取链表长度
 int GetLengthList(const LPLIST List); //返回长度
 //14.反转链表
 // void ReverseList()
 //15.结点交换数据
 // 
Others:
FunctionList:
Histroy:
********************************************/
#include <stdio.h>
#include <stdlib.h>

typedef struct SingleList {
 int data; //数据域
 struct SingleList *next; //指向下个的指针
}LIST, *LPLIST;

int GetNode(const LPLIST List, int pos, LPLIST e);
void PrintList(const LPLIST List);
int InsertNodeHead(LPLIST *List, int data); 
int InsertNodeTail(LPLIST *List, int data);
int InsertNodePos(LPLIST *List, int data, int pos); //pos从1开始
int IsEmptyList(LPLIST List);
int LocateNode(const LPLIST List, const LPLIST e); //返回值是元素的位置,0表示没找到,第1个是1
int DeletePos(LPLIST *List, int pos); //pos从1开始 返回1成功 0失败
void SortList(LPLIST *List);
void SortList_Insert(LPLIST *List,LPLIST node); //用来辅助上面的排序函数
void DeleteList(LPLIST *List);
int GetLengthList(const LPLIST List); //返回长度

int main() {
 LPLIST List = NULL; //创建1个无头结点的空链表
 if (IsEmptyList(List)) printf("判断IsEmptyList:是空表!====>");
 PrintList(List); //空表打印
 printf("头插法,写入10,20,30====>");
 InsertNodeHead(&List, 10); //头插法写入10
 InsertNodeHead(&List, 20); //头插法写入20
 InsertNodeHead(&List, 30); //头插法写入30
 PrintList(List); //输出 30 20 10
 printf("尾插法,写入40,50,60====>");
 InsertNodeTail(&List, 40); //尾插法 40
 InsertNodeTail(&List, 50); //尾插法 50
 InsertNodeTail(&List, 60); //尾插法 60
 PrintList(List); //输出 30 20 10 40 50 60
 printf("定位插入1-70,2-80,3-90====>");
 InsertNodePos(&List, 70, 1); //指定位置1插入 70
 InsertNodePos(&List, 80, 2); //指定位置2插入 80
 InsertNodePos(&List, 90, 3); //指定位置3插入 90
 PrintList(List); //输出 30 20 10 40 50 60
 LIST e = {0};
 GetNode(List, 1, &e);
 printf("获取位置1的元素值====>");
 printf("GetNode(1)=%d\n", e.data);
 GetNode(List, 7, &e);
 printf("获取位置7的元素值====>");
 printf("GetNode(7)=%d\n", e.data);
 if (!IsEmptyList(List)) printf("判断IsEmptyList:非空表!\n");
 e.data = 20;
 printf("查找元素值为20的位置====>");
 printf("%d的位置在%d\n", e.data, LocateNode(List, &e));
 PrintList(List);
 if(DeletePos(&List, 3))
 printf("删除第3个位置====>");
 PrintList(List);
 if (DeletePos(&List, 1))
 printf("删除第1个位置====>");
 PrintList(List);
 if (DeletePos(&List, 7))
 printf("删除第7个位置====>");
 PrintList(List);
 if (!DeletePos(&List, 7))
 printf("删除第7个位置====>失败");
 PrintList(List);
 printf("排序====>");
 SortList(&List); //排序
 PrintList(List);
 printf("删除所有元素====>");
 DeleteList(&List);
 PrintList(List);
 return 0;
}
int GetNode(const LPLIST List, int pos, LPLIST e) {
 if (pos < 1) return 0; //pos不对返回0
 LPLIST p = List;
 int j = 1;
 while (NULL!=p && j < pos) {
 p = p->next;
 ++j;
 }//这里 找到的话 j==pos,并且p不能为NULL
 if (NULL == p || j < pos) return 0;
 e->data = p->data;
 e->next = p->next;
 return 1;
}

void PrintList(const LPLIST List) {
 LPLIST p = List; //设置临时链表指针p
 if (NULL == p) {
 printf("空链表\n");
 return;
 }
 while (p) {
 printf("%d->", p->data); //打印
 p = p->next; //指向下一个
 }
 printf("\n");
}
int InsertNodeHead(LPLIST *List, int data) {
 //以后写,这个新结点分配内存,应该放在 CreateNode()函数里面
 LPLIST newNode = (LPLIST)malloc(sizeof(LIST)); //新结点分配内存
 if (newNode == NULL) return 0;
 newNode->data = data; //新结点赋值数据
 if (NULL == *List) { //是空表,新结点是链表头,next指向NULL
 newNode->next = NULL; //
 *List = newNode;
 }
 else { //链表非空,把新结点的next指向当前链表头,当前链表头指向新结点
 newNode->next = *List;
 *List = newNode;
 }
 return 1;
}

int InsertNodeTail(LPLIST *List, int data) {
 LPLIST newNode = (LPLIST)malloc(sizeof(LIST)); //新结点分配内存
 if (newNode == NULL) return 0;
 newNode->data = data;
 newNode->next = NULL; //因为尾插,所以肯定是NULL
 if (NULL == *List) { //是空表,尾插也是:新结点是链表头,next指向NULL
 *List = newNode;
 }
 else { //非空表,尾插:找到结尾处,将结尾结点的next指向newNode
 LPLIST p = *List;
 while (p->next){
 p = p->next; 
 }
 p->next = newNode;
 }
 return 1;
}

int InsertNodePos(LPLIST *List, int data, int pos) { //插入指定位置,pos从1开始
 //先判断pos的位置是否合法
 if (pos < 1) return 0; //pos从1开始
 if (NULL == *List && pos > 1) return 0; //空表,pos只能=1
 if (1 == pos) { //在第1的位置插入,就是首结点 直接调用头插法了
 if (InsertNodeHead(List, data)) return 1;
 else return 0;
 }
 //下面是从第2个结点开始的,pos>1的情况(至少=2)
 LPLIST p=*List; //设定2个指针 p和q, p在前,q在后
 int j = 2; //当前指针p位置
 while (p && j < pos) {//寻找pos位置
 p = p->next;
 ++j;
 } //找到的话,应该 j == pos
 if (j < pos) return 0; //没有该位置
 //下面就是在pos的位置上,p指向位置前1位,q是当前插入的位置
 LPLIST newNode = (LPLIST)malloc(sizeof(LIST)); //新结点分配内存
 if (newNode == NULL) return 0;
 newNode->data = data;
 newNode->next = p->next;
 p->next = newNode;
 return 1;
}
int IsEmptyList(LPLIST List) {
 return NULL == List;
}
int LocateNode(const LPLIST List, const LPLIST e) { //返回值是元素的位置,0表示没找到,第1个是1
 LPLIST p = List;
 int pos = 1;
 while (NULL != p && p->data != e->data) {
 p = p->next;
 ++pos;
 }
 if (NULL == p) return 0;
 return pos;
}

int DeletePos(LPLIST *List, int pos) { //pos从1开始
 if (pos < 1 || NULL == *List) return 0;
 LPLIST p = *List;
 if (pos == 1) { //删除第1个
 *List = (*List)->next;
 free(p); //释放空间
 return 1;
 }
 int j = 2;
 while (NULL != p &&j < pos) {
 p = p->next;
 ++j;
 }
 if (NULL == p->next || j < pos) return 0; //删除位置是空,或者没有到pos就没了
 LPLIST q=p->next;
 p->next = p->next->next;
 free(q); //释放空间
 return 1;
}

void SortList(LPLIST *List) { //从小到大排序
 //int length = GetLengthList(*List); //获取链表长度
 //if (length < 2) return; //只有0个或1个不要排序了
 if (NULL == *List) return; //空表不需要排序
 LPLIST *head = List; //头部指针的指针
 LPLIST cur = (*head)->next, tmp = cur;
 (*head)->next = NULL; //新的链表的 next 先中止,这样就目前只有1个首结点了
 //把后面的 一个一个 插入到新的链表里
 while (tmp != NULL) {
 cur = tmp;
 tmp = tmp->next;
 SortList_Insert(head, cur);
 }
}

void SortList_Insert(LPLIST *List, LPLIST node) { //用来辅助上面的排序函数
 //LPLIST *List 是排序后的链表,node是要按照从小到大插进去的(插入法排序)
 if (node->data < (*List)->data) { //比新链的首结点小,插在新结点前面
 node->next = *List;
 *List = node;
 return;
 }
 LPLIST p = *List;
 while (p->next != NULL&&node->data > p->next->data) {
 p = p->next;
 }
 if (NULL == p->next) { //后面没结点了
 p->next = node;
 node->next = NULL;
 return;
 }
 //后面还有结点的情况
 node->next = p->next;
 p->next = node;
}

void DeleteList(LPLIST *List) {
 if (NULL == *List) return;
 LPLIST p = *List,q=p;
 while (NULL != p) {
 p = p->next;
 free(q);
 q = p;
 }
 *List = NULL;
 return;
}

int GetLengthList(const LPLIST List) { //返回长度
 int length = 0;
 LPLIST p = List;
 while (NULL != p) {
 p = p->next;
 ++length;
 }
 return length;
}

(2017-02-28 www.vsppc.com)

学习笔记未经允许不得转载:PPC的C/C++和人工智能学习笔记 » C语言基础(15-1)_链表练习

分享到:更多 ()

评论 71

评论前必须登录!