#ifndef __LINKEDLIST_H__
#define __LINKEDLIST_H__
// LinkedListd.h
/*===========================线性单链表================================*/
/* 以下是关于线性表链接存储(单链表)操作的18种算法 */
/* 1.初始化线性表,即置单链表的表头指针为空 */
/* 2.创建线性表,此函数输入负数终止读取数据 */
/* 3.打印链表,链表的遍历 */
/* 4.清除线性表L中的所有元素,即释放单链表L中所有的结点,使之成为一个空表 */
/* 5.返回单链表的长度 */
/* 6.检查单链表是否为空,若为空则返回1,否则返回0 */
/* 7.返回单链表中第pos个结点中的元素,若pos超出范围,则停止程序运行 */
/* 8.从单链表中查找具有给定值x的第一个元素,若查找成功则返回该结点data域的存储地址,否则返回NULL */
/* 9.把单链表中第pos个结点的值修改为x的值,若修改成功返回1,否则返回0 */
/* 10.向单链表的表头插入一个元素 */
/* 11.向单链表的末尾添加一个元素 */
/* 12.向单链表中第pos个结点位置插入元素为x的结点,若插入成功返回1,否则返回0 */
/* 13.向有序单链表中插入元素x结点,使得插入后仍然有序 */
/* 14.从单链表中删除表头结点,并把该结点的值返回,若删除失败则停止程序运行 */
/* 15.从单链表中删除表尾结点并返回它的值,若删除失败则停止程序运行 */
/* 16.从单链表中删除第pos个结点并返回它的值,若删除失败则停止程序运行 */
/* 17.从单链表中删除值为x的第一个结点,若删除成功则返回1,否则返回0 */
/* 18.交换2个元素的位置 */
/* 19.将线性表进行快速排序 */
/*========================================================================*/
typedef struct tagNode
{
int data;
tagNode *Next;
}Node;
typedef Node* LinkedList;
/* 1.初始化线性表,即置单链表的表头指针为空 */
void InitList(LinkedList* list);
/* 3.打印链表,链表的遍历 */
void PrintList(LinkedList list);
/* 4.清除线性表L中的所有元素,即释放单链表L中所有的结点,使之成为一个空表 */
void FreeList(LinkedList* list);
/* 5.返回单链表的长度 */
int ListLenghth(LinkedList list);
/* 6.检查单链表是否为空,若为空则返回1,否则返回0 */
int IsListEmpty(LinkedList list);
/* 7.返回单链表中第pos个结点中的元素,若pos超出范围,则停止程序运行 */
int GetData(LinkedList list, int pos);
/* 8.从单链表中查找具有给定值x的第一个元素,若查找成功则返回该结点data域的存储地址,否则返回NULL */
int FindData(LinkedList list, int value);
/* 9.把单链表中第pos个结点的值修改为x的值,若修改成功返回1,否则返回0 */
int ModifyData(LinkedList* list, int pos, int value);
/* 10.向单链表的表头插入一个元素 */
void InsertHeadData(LinkedList* list, int value);
/* 11.向单链表的末尾添加一个元素 */
void InsertEndData(LinkedList* list, int value);
/* 12.向单链表中第pos个结点位置插入元素为x的结点,若插入成功返回1,否则返回0 */
int InsertData(LinkedList* list, int pos, int value);
/* 13.向有序单链表中插入元素x结点,使得插入后仍然有序 */
/* 14.从单链表中删除表头结点,并把该结点的值返回,若删除失败则停止程序运行 */
int DeleteHeadData(LinkedList* list);
/* 15.从单链表中删除表尾结点并返回它的值,若删除失败则停止程序运行 */
int DeleteEndData(LinkedList* list);
/* 16.从单链表中删除第pos个结点并返回它的值,若删除失败则停止程序运行 */
int DeleteData(LinkedList* list, int pos);
/* 17.从单链表中删除值为x的第一个结点,若删除成功则返回1,否则返回0 */
int DeleteFstData(LinkedList* list, int value);
/* 18.交换2个元素的位置 */
/* 19.将线性表进行快速排序 */
#endif //__LINKEDLIST_H__
// LinkedList.cpp #include "LinkedList.h" #include <stdlib.h> #include <stdio.h> /* 1.初始化线性表,即置单链表的表头指针为空 */ void InitList(LinkedList* list) { *list = NULL; //(*list)->Next = NULL; } /* 3.打印链表,链表的遍历 */ void PrintList(LinkedList list) { while (NULL != list) { printf("%d\n", list->data); list = list->Next; } } /* 4.清除线性表L中的所有元素,即释放单链表L中所有的结点,使之成为一个空表 */ void FreeList(LinkedList* list) { if (NULL == (*list)) return; Node* pNode = *list; while (pNode->Next != NULL) { pNode = (*list)->Next; free(*list); *list = pNode; } } /* 5.返回单链表的长度 */ int ListLenghth(LinkedList list) { int cnt = 0; if (NULL == list) return 0; while (list->Next != NULL) { cnt++; list = list->Next; } return cnt; } /* 6.检查单链表是否为空,若为空则返回1,否则返回0 */ int IsListEmpty(LinkedList list) { if (NULL == list) return 1; return 0; } /* 7.返回单链表中第pos个结点中的元素,若pos超出范围,则停止程序运行 */ int GetData(LinkedList list, int pos) { int value = 0, cnt = 0;; if (NULL == list || pos < 0) return -1; Node* pNode = list; while (pNode->Next != NULL) { cnt++; if (cnt == pos) { value = pNode->data; break; } pNode = pNode->Next; } return value; } /* 8.从单链表中查找具有给定值x的第一个元素,若查找成功则返回该结点data域的存储地址,否则返回NULL */ int FindData(LinkedList list, int value) { int pos = -1; if (NULL == list) return -1; while (list->Next != NULL) { pos++; if (value == list->data) break; list = list->Next; } // 遍历完,都未找到定值x if (NULL == list->Next) pos = -1; return pos; } /* 9.把单链表中第pos个结点的值修改为x的值,若修改成功返回1,否则返回0 */ int ModifyData(LinkedList* list, int pos, int value) { if (NULL == list) return 0; int cnt = 0; Node *Head = NULL; Head = *list; while ((*list)->Next != NULL) { if (pos == cnt) (*list)->data = value; (*list) = (*list)->Next; cnt++; } if ((*list)->Next != NULL) return 1; *list = Head; return 0; } /* 10.向单链表的表头插入一个元素 */ void InsertHeadData(LinkedList* list, int value) { Node* pNode = (Node*) malloc(sizeof(Node)); pNode->data = value; if (NULL == *list) { pNode->Next = NULL; *list = pNode; return; } pNode->Next = (*list); *list = pNode; return; } /* 11.向单链表的末尾添加一个元素 */ void InsertEndData(LinkedList* list, int value) { Node *pNode = (Node*) malloc(sizeof(Node)); Node *Head = *list; pNode->data = value; pNode->Next = NULL; if (NULL == *list) { *list = pNode; return; } while ((*list)->Next != NULL) { *list = (*list)->Next; } (*list)->Next = pNode; *list = Head; return; } /* 12.向单链表中第pos个结点位置插入元素为x的结点,若插入成功返回1,否则返回0 */ int InsertData(LinkedList* list, int pos, int value) { int cnt = 0; Node *Head = NULL, *pNode = NULL; Head = *list; pNode = (Node *) malloc(sizeof(Node)); pNode->data = value; while ((*list)->Next != NULL) { cnt++; (*list) = (*list)->Next; if (cnt == pos - 1) { pNode->Next = (*list)->Next; (*list)->Next = pNode; } } *list = Head; return 1; } /* 13.向有序单链表中插入元素x结点,使得插入后仍然有序 */ /* 14.从单链表中删除表头结点,并把该结点的值返回,若删除失败则停止程序运行 */ int DeleteHeadData(LinkedList* list) { int value = 0; if (NULL == *list) return 0; Node *Head = NULL; if ((*list)->Next != NULL) Head = (*list)->Next; value = (*list)->data; free((*list)); *list = Head; return value; } /* 15.从单链表中删除表尾结点并返回它的值,若删除失败则停止程序运行 */ int DeleteEndData(LinkedList* list) { int value = 0; if (NULL == *list) return 0; Node *Head = NULL; if ((*list)->Next == NULL) { value = (*list)->data; free(*list); *list = NULL; } Head = *list; while (((*list)->Next)->Next != NULL) { *list = (*list)->Next; } value = ((*list)->Next)->data; free((*list)->Next); (*list)->Next = NULL; *list = Head; return value; } /* 16.从单链表中删除第pos个结点并返回它的值,若删除失败则停止程序运行 */ int DeleteData(LinkedList* list, int pos) { int value = 0, cnt = 0; if (NULL == *list) return 0; Node *Head = NULL, *pNode = NULL; Head = *list; while ((*list)->Next != NULL) { if (cnt == pos - 1) { pNode = (*list)->Next; (*list)->Next = (pNode)->Next; value = pNode->data; free(pNode); break; } else *list = (*list)->Next; cnt++; } *list = Head; return value; } /* 17.从单链表中删除值为x的第一个结点,若删除成功则返回1,否则返回0 */ int DeleteFstData(LinkedList* list, int value) { int cnt = 0; if (NULL == *list) return cnt; Node *Head = NULL; Head = *list; // 第一个即满足要求 if (value == (*list)->data) { if ((*list)->Next != NULL) Head = (*list)->Next; else Head = NULL; free(*list); return 1; } while ((*list)->Next != NULL) { if (((*list)->Next)->data == value) { *list = ((*list)->Next)->Next; free((*list)->Next); break; } else { (*list) = (*list)->Next; } } *list = Head; return cnt; } /* 18.交换2个元素的位置 */ /* 19.将线性表进行快速排序 */
// DemoMain.cpp #include <stdlib.h> #include <stdio.h> #include "LinkedList.h" int main() { int Length = 10; LinkedList list = NULL; Node *TempNode = NULL, *Head = NULL; InitList(&list); list = (LinkedList) malloc(sizeof(Node)); list->data = 0; list->Next = NULL; Head = list; for (int dIndex = 1; dIndex < 10; dIndex++) { TempNode = (Node *) malloc(sizeof(Node)); TempNode->data = dIndex; TempNode->Next = NULL; list->Next = TempNode; list = list->Next; } list = Head; PrintList(list); int len = ListLenghth(list); printf("List Length: %d\n", len); if (0 == IsListEmpty(list)) { printf("List is Not Empty!\n"); } int data = GetData(list, 5); printf("The 5th data of list is: %d\n", data); int pos = FindData(list, 5); printf("the pos of 5 in list is: %d\n", pos); ModifyData(&list, 5, 99); printf("Change 5th pos of list to 99...\n"); PrintList(list); InsertHeadData(&list, 88); printf("Insert 88 to Head of List\n"); PrintList(list); InsertEndData(&list, 66); printf("INsert 66 to End of List\n"); PrintList(list); InsertData(&list, 2, 22); printf("Insert 22 to 2th of List\n"); PrintList(list); DeleteHeadData(&list); printf("Delete Head Data of List\n"); PrintList(list); DeleteEndData(&list); printf("Delete End Data of List\n"); PrintList(list); DeleteData(&list, 2); printf("Delete 2th of List\n"); PrintList(list); return 0; }