第一章 链表

单链表无头节点

01.函数声明linkedList.h

02.数值检查check_list.cpp

03.显示show.cpp

04.插入操作insert.cpp

05. 删除操作delete.cpp

06. 输入数值input.cpp

07. 释放内存free.cpp

08. 节点计数itm_cunt.cpp

09. 冒泡排序sort.cpp

单链表有头结点

声明linked_list.h

函数定义linked_list.cpp

list.cpp

第二章 链式栈与队列

链式栈stack

链式队列queue

第一章 链表

单链表无头节点

01.函数声明linkedList.h

#include <stdio.h>#include <stdlib.h>struct NODE{int value;struct NODE *next;};typedef struct NODE Node;extern Node *root;//这里的root是在link_main文件中的定义的,同时应用于input.cpp文件，该文件中没有定义指针root，//其结果是在调用过input函数之后，root值改变，不再为NULL；bool sell_insert(Node **,int ); //插入节点函数void show(Node *);//显示链表数据函数void input_data(Node **);//输入链表数据函数void free_list(Node **);//释放链表内存函数unsigned int count(Node *);//链表节点计数函数bool check(Node *,int);//检查输入的数据是否在聊表中已经存在的函数void sort(Node *);//链表排序函数――冒泡法void delete_data(Node **,int); //删除节点函数

02.数值检查check_list.cpp

/*查找从root根节点之后的各个节点数据域，是否存在value相同的值，如果找到相同值* return 返回 true* 否则 return false*/bool check(Node *root,int value){Node *current;current = root;while(current != NULL){if(current->value != value)current = current->next;elsebreak;}if(current != NULL)return true; //当顺序遍历完整个linkedlist 仍然无value值，则返回falseelse return false;}

03.显示show.cpp

#include "sll_node.h"/*显示函数*/bool show(Node *root){bool retn = true;Node *current; if(root == NULL){printf("No data entered.");retn = false;goto END;}current = root;while(current != NULL){printf(" %d ",current->value);current = current->next;retn = true;}END:return retn;}

04.插入操作insert.cpp

#include "sll_node.h"/*插入操作* IN: insert list position (**)phead and Elementype new_value* OUT: Operation success blag true?false?* */bool sell_insert(Node **phead,int new_value){Node *current = NULL;Node *previous = NULL;Node *newn = NULL;current = *phead;while(current != NULL && current->value < new_value){previous = current;current = current->next;}newn = (Node *)malloc(sizeof(Node)); //在堆上开辟一个新节点内存newn，开辟失败返回falseif(newn == NULL)return false;newn->value = new_value; //将值new_value传入新节点中newn->next = current; //先将后继的链表节点接入，防止脱链if(previous==NULL)//如果该节点插入的当前节点为首节点，将newn新节点置为头结点*phead = newn;elseprevious->next = newn; //否则，链接前驱节点return true;}

05. 删除操作delete.cpp

#include "sll_node.h"/*删除节点操作* IN：链表头结点，phead；要删除的数据* OUT：操作成功标志位* */booldelete_data(Node **phead, int delete_value) {Node *current = NULL;Node *previous = NULL;Node *next = NULL;Node *pt = NULL;current = *phead;if(current == NULL){ //链表非空return false;}while (current->value != delete_value && current->next != NULL) { //遍历所有链表节点previous = current;current = current->next;next = current->next;}if (current->value == delete_value){if (previous == NULL)*phead = current->next; //删除头结点elseprevious->next = next; //非头结点pt = current;free(pt); //删除节点之后必须释放内存return true；}else{return false;}}

06. 输入数值input.cpp

#include "sll_node.h"/*输入函数*/voidinput_data(Node **phead){int value;Node *current,*prev;root = *phead;puts("Enter the first value(q to end):");while(scanf("%d",&value)==1){while(getchar() != '\n')continue;current = (Node *)malloc(sizeof(Node));if(root == NULL)root = current;elseprev->next = current;current->next = NULL;current->value = value;puts("Enter the next value(q to end):");prev = current;}}

07. 释放内存free.cpp

#include "sll_node.h"/*释放内存函数*/void free_list(Node **phead){Node *psave;while(*phead != NULL){psave = (*phead)->next;free(*phead);*phead = psave;}}

08. 节点计数itm_cunt.cpp

#include "sll_node.h"/*节点计数函数*/unsigned int count(Node *root){unsigned int count = 0;while(root != NULL){++count;root = root->next;}return count;}

09. 冒泡排序sort.cpp

#include "sll_node.h"/*冒泡法排序链表函数――不改变节点位置，只改变节点中数据的存储位置*/void sort(Node *root){Node *current;Node *s;for(current = root;current->next != NULL;current = current->next){for(s = root;s->next != NULL;s = s->next){if(s->value > s->next->value){int temp;temp = s->value;s->value = s->next->value;s->next->value = temp;}}}}

单链表有头结点

声明linked_list.h

/*** Created with Clion IDEA.* Description: * * User: haowang* Date: -03-12* Time: 09:56*//**************************************************************************************************************以下为操作链表的算法，该链表为单链表。链表以头指针为索引，头指针指向头节点，头节点指向首节点，以此类推，直到尾节点。头节点中不存放数据，只存放指向首节点的指针，设置头节点的目的是为了方便对链表的操作，如果不设置头节点，而是直接由头指针指向首节点，这样在对头指针后的节点进行插入删除操作时就会与其他节点进行该操作时有所不同，便要作为一种特殊情况来分析**************************************************************************************************************/#ifndef GITHUB_PRO_LINKED_LIST_H#define GITHUB_PRO_LINKED_LIST_H#include<stdio.h>#include<stdlib.h>typedef struct Node//定义节点Node结构体{int data; //数据域struct Node *pNext; //指针域，pNext指针指向下一个Node结构体}NODE,*PNODE;extern Node *PNODE ;//结构体指针，指向creat_list的首地址void traverse_list(PNODE);bool is_empty(PNODE);int length_list(PNODE);void sort_list(PNODE);bool insert_list(PNODE,int,int);bool delete_list(PNODE,int,int *);void clear_list(PNODE);#endif //GITHUB_PRO_LINKED_LIST_H

函数定义linked_list.cpp

/*** Created with Clion IDEA.* Description:* User: haowang* Date: -03-12* Time: 10:02*/#include "linked_list.h"#include <stdlib.h>#include <stdio.h>/*创建一个链表,并返回头指针*/PNODE create_list() {int val;PNODEpHead = (PNODE) malloc(sizeof(NODE));PNODEpCurrent = pHead;pCurrent->pNext = NULL;if (NULL == pHead) {printf("pHead malloc failed!");exit(-1);}printf("Input first data(q to quit):");while (scanf("%d", &val) == 1) {PNODEpNew = (PNODE) malloc(sizeof(NODE));if (NULL == pNew) {printf("pNew malloc failed!");exit(-1);}pNew->data = val;pCurrent->pNext = pNew;pNew->pNext = NULL;pCurrent = pNew;printf("Input next data(q to quit):");}return pHead;}/*遍历链表*/void traverse_list(PNODE pHead) {PNODEpCurrent = pHead->pNext;printf("now dataes in the list are:\n");while (pCurrent != NULL) {printf("%d ", pCurrent->data);pCurrent = pCurrent->pNext;}printf("\n");return;}/*判断链表是否为空*/bool is_empty(PNODE pNode) {if (NULL == pNode->pNext)return true;elsereturn false;}/*求链表长度，即节点总数（不计入头节点）*/int length_list(PNODE pNode) {int count = 0;PNODEpCurrent = pNode->pNext;while (pCurrent != NULL) {count++;pCurrent = pCurrent->pNext;}return count;}/*冒泡法对链表排序*/void sort_list(PNODE pHead) {PNODEp, q;int temp;for (p = pHead->pNext; p != NULL; p = p->pNext)for (q = p->pNext; q != NULL; q = q->pNext) {if (p->data > q->data) {temp = p->data;p->data = q->data;q->data = temp;}}return;}/*在第pos个节点的后面插入一个新的节点，该节点中的数据为val*/bool insert_list(PNODE pHead, int pos, int val) {int i = 0;PNODEp = pHead;//i为0时，p指向第0个节点（这里指没有实际数据的头节点，不计入链表节点总数），//i为1时，p指向第1个节点，i为几，p就指向第几个节点while (p != NULL && i < pos) {p = p->pNext;i++;}//当pos的值大于链表长度时，便会出现这种情况if (i > pos || p == NULL)return false;PNODEpNew = (PNODE) malloc(sizeof(NODE));if (NULL == pNew) {printf("pNew malloc failed!");exit(-1);}pNew->data = val;pNew->pNext = p->pNext;p->pNext = pNew;return true;}/*删除第pos个节点，并将删除的数据保存在pData指针所指向的位置*/bool delete_list(PNODE pHead, int pos, int *pData) {int i = 0;PNODEp = pHead;//p最终指向第pos个节点前面的节点//如果下面两句分别改为while(p!=NULL && i<pos)和if(i>pos || p==NULL)，则p最终指向第pos个节点，//这样因为得不到第pos个节点前面的那个节点，因此无法将pos前后两个节点连结起来while (p->pNext != NULL && i < pos - 1) {p = p->pNext;i++;}//当pos的值大于链表长度时，便会出现这种情况if (i > pos - 1 || p->pNext == NULL)return false;PNODEq = p->pNext;*pData = q->data;p->pNext = p->pNext->pNext;free(q);q = NULL;return true;}/*清空链表，即使链表只剩下头节点（头节点中没有数据）*/void clear_list(PNODE pHead) {PNODEp = pHead->pNext;PNODEr = NULL;while (p != NULL) {r = p->pNext;free(p);p = r;}pHead->pNext = NULL;return;}

list.cpp

/**************************************************************************************************************以下为操作链表的算法，该链表为单链表。链表以头指针为索引，头指针指向头节点，头节点指向首节点，以此类推，直到尾节点。头节点中不存放数据，只存放指向首节点的指针，设置头节点的目的是为了方便对链表的操作，如果不设置头节点，而是直接由头指针指向首节点，这样在对头指针后的节点进行插入删除操作时就会与其他节点进行该操作时有所不同，便要作为一种特殊情况来分析**************************************************************************************************************/#include<stdio.h>#include<stdlib.h>#include "linked_list.h"PNODE create_list();//结构体指针，指向creat_list的首地址int main(void){int len;int data_del;PNODE pHead = NULL;//创建链表并遍历输出pHead = create_list();traverse_list(pHead);//求链表长度，并输出len = length_list(pHead);if(!is_empty(pHead))printf("the length of the list is:%d\n",len);//向链表中插入数据，并重新遍历输出if(insert_list(pHead,3,78))printf("insert succeed,");elseprintf("insert failed,");traverse_list(pHead);//从链表中删除数据，并重新遍历输出if(delete_list(pHead,3,&data_del)){printf("delete succeed,the deleted data is:%d\n",data_del);}elseprintf("delete failed,");traverse_list(pHead);//对链表排序，重新遍历输出sort_list(pHead);printf("After sorted,");traverse_list(pHead);//清空链表，遍历输出（无数据输出）clear_list(pHead);printf("After cleared,");traverse_list(pHead);return 0;}

第二章 链式栈与队列

链式栈stack

/**************************************************************************************************************以下为操作栈的算法，该栈为动态栈。在该栈中，pTop指向的节点中存放该栈的栈顶数据pBottom指向的节点的上一个节点存放该栈的栈底数据，pBottom指向的节点中不存放有效数据，这样做的目的是为了在进行入栈和出栈时方便对栈的操作，而用考虑特殊情况**************************************************************************************************************/#include<stdio.h>#include<stdlib.h>typedef struct Node{int data;struct Node *pNext;}NODE,*PNODE;typedef struct Stack{PNODE pTop;PNODE pBottom;}STACK,*PSTACK;PSTACK create_stack();void push_stack(PSTACK,int);void traverse_stack(PSTACK);bool pop_stack(PSTACK,int *);bool is_empty(PSTACK);void clear_stack(PSTACK);int main(){int data_pop;//创建一个空的栈，pS指针指向该栈PSTACK pS = create_stack();//向该栈中压入数据，遍历该栈并输出栈中的数据push_stack(pS,2);push_stack(pS,6);push_stack(pS,28);traverse_stack(pS);//从该栈中推出数据，遍历该栈并输出栈中的数据if(pop_stack(pS,&data_pop))printf("pop succeed,the data poped out is:%d\n",data_pop);else printf("pop failed\n");traverse_stack(pS);//清空栈，遍历该栈并输出栈中的数据clear_stack(pS);printf("data cleared!\n");traverse_stack(pS);return 0;}/*创建一个空栈,并返回指向该栈的指针*/PSTACK create_stack(){PSTACK pS = (PSTACK)malloc(sizeof(STACK));pS->pTop = (PNODE)malloc(sizeof(NODE));if(NULL==pS || NULL==pS->pTop){printf("malloc failed");exit(-1);}else{pS->pBottom = pS->pTop;pS->pBottom->pNext = NULL;}return pS;}/*判断该栈是否为空*/bool is_empty(PSTACK pS){if(pS->pTop == pS->pBottom)return true;elsereturn false;}/*向pS指针指向的栈中压入数据val*/void push_stack(PSTACK pS,int val){PNODE pNew = (PNODE)malloc(sizeof(NODE));if(NULL==pNew){printf("malloc failed");exit(-1);}else{pNew->data = val;pNew->pNext = pS->pTop;pS->pTop = pNew;}return ;}/*从栈中推出数据，并将推出的数据保存在pData指针所指向的位置*/bool pop_stack(PSTACK pS,int *pData){if(is_empty(pS))return false;else{PNODE p = pS->pTop;*pData = p->data;pS->pTop = p->pNext;free(p);p = NULL;return true;}}/*遍历栈，并自栈顶向栈底输出栈中的数据*/void traverse_stack(PSTACK pS){PNODE pCurrent = pS->pTop; printf("Now datas int the stack are:\n");while(pCurrent != pS->pBottom){printf("%d ",pCurrent->data);pCurrent = pCurrent->pNext;}printf("\n");return ;}/*清空栈，即将其还原为空栈*/void clear_stack(PSTACK pS){if(is_empty(pS))return ;else{PNODE p = pS->pTop;PNODE r = NULL;while(p != pS->pBottom){r = p->pNext;free(p);p = r;}pS->pTop = pS->pBottom;}}

链式队列queue

/*******************************************************************该队列为链式队列，初建队列时，队头和队尾均指向头结点，头结点中不存放数据，只存放指针，头结点的下一个节点才开始存放数据，这这样做的目的是为了在入队和出队时方便对队列的操作，而不用考虑特殊情况。*******************************************************************/#include<stdio.h>#include<stdlib.h>typedef struct Node{int data;struct Node *pNext;}NODE,*PNODE;typedef struct Queue{PNODE front; //队头指针PNODE rear; //队尾指针}QUEUE,*PQUEUE;PQUEUE create_queue();bool is_empty(PQUEUE);void en_queue(PQUEUE, int);bool de_queue(PQUEUE,int *);void destroy_queue(PQUEUE);void traverse_queue(PQUEUE);int main(){int data_de = 0; //用来保存出队的元素值//创建队列并进行入队测试PQUEUE pS = create_queue();en_queue(pS,2);en_queue(pS,4);en_queue(pS,6);traverse_queue(pS);//出队测试if(de_queue(pS,&data_de))printf("delete succeed,the deleted data is: %d\n",data_de);elseprintf("queue is empty! delete falied!\n");traverse_queue(pS);//销毁队列测试destroy_queue(pS);printf("queue destroyed!\n");traverse_queue(pS);return 0;}/*创建一个空队列，队头指针和队尾指针都指向头结点，头结点中不存放数据，只存放指针*/PQUEUE create_queue(){PQUEUE pS = (PQUEUE)malloc(sizeof(Queue));pS->front = (PNODE)malloc(sizeof(NODE));if(!pS || !pS->front){printf("pS or front malloc failed!!");exit(-1);}else{pS->rear = pS->front;pS->front->pNext = NULL;}return pS;}/*判断队列是否为空*/bool is_empty(PQUEUE pS){if(pS->front == pS->rear)return true;elsereturn false;}/*进队函数，从队尾进队，队头指针保持不变*/void en_queue(PQUEUE pS, int e){PNODE pNew = (PNODE)malloc(sizeof(NODE));if(!pNew){printf("pNew malloc failed");exit(-1);}else{pNew->data = e;pNew->pNext = NULL;pS->rear->pNext = pNew;pS->rear = pNew;}return;}/*出队函数，从队头出队，队尾指针保持不变，但当最后一个元素出队时，需要对队尾指针重新赋值，使其指向头结点*/bool de_queue(PQUEUE pS,int *pData){if(is_empty(pS))return false;else{PNODE p = pS->front->pNext;*pData = p->data;pS->front->pNext = p->pNext;//这里是队列头元素出队的特殊情况，一般情况下，删除队头元素时//仅需修改头结点中的指针，但当队列中最后一个元素被删除时，//队列尾指针也丢失了，因此需对队尾指针重新赋值（指向头结点）。if(pS->rear == p) pS->rear = pS->front;free(p);}return true;}/*遍历队列，从对头向队尾依次输出队中的元素*/void traverse_queue(PQUEUE pS){if(is_empty(pS))printf("there is no data in the queue!\n");else{PNODE pCurrent = pS->front->pNext; printf("Now datas int the queue are:\n");while(pCurrent){printf("%d ",pCurrent->data);pCurrent = pCurrent->pNext;}printf("\n");}return;}/*销毁队列,头结点也被销毁,最后也将pS节点销毁，并将其指向为空，避免垂直指针的产生*/void destroy_queue(PQUEUE pS){if(is_empty(pS))return;else{while(pS->front){pS->rear = pS->front->pNext;free(pS->front);pS->front = pS->rear;}}free(pS);pS = 0;return;}

#include <iostream>#include "stdlib.h"#include "string.h"#include "math.h"#include <time.h>using namespace std;typedef struct Node {int data;struct Node *next ;} Node, *Pnode;typedef struct Node *LinkedList;bool getElement(Pnode L, int idx, int *e) {int j = 1;Pnode p = L;p = L->next;for (; p != NULL && j < idx; ++j) {p = p->next;}if (!p || j > idx) {std::cerr << "ERROR" << std::endl;return false;}(*e) = p->data;return true;}int main() {int e = 0;srand((unsigned)time(NULL));Pnode newList = new Node; //头结点Pnode pNode = newList; //创建临时Pnode类型的pNode变量用于连接链表pNode ->next = NULL;for (int i = 1; i < 100; ++i) {Pnode pNew = new Node;pNew ->data = rand() % 100;pNew ->next =NULL;pNode ->next = pNew;pNode = pNew;}if (getElement(newList, 6, &e)) {cout << "Get the element in the list " << e << endl;}delete[](newList);return 0;}