/**
* @author huihut
* @E-mail:huihut@outlook.com
* @version 創(chuàng)建時間：2016年9月18日
* 說明：本程序?qū)崿F(xiàn)了一個單鏈表。
*/
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
//5個常量定義
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
//類型定義
typedef int Status;
typedef int ElemType;
//測試程序長度定義
#define LONGTH 5
//鏈表的類型
typedef struct LNode {
? ? ElemType data;
? ? struct LNode *next;
} LNode, *LinkList;
Status InitList_L(LinkList &L);
Status DestroyList_L(LinkList &L);
Status ClearList_L(LinkList &L);
Status ListEmpty_L(LinkList L);
int ListLength_L(LinkList L);
LNode* Search_L(LinkList L, ElemType e);
LNode* NextElem_L(LNode *p);
Status InsertAfter_L(LNode *p, LNode *q);
Status DeleteAfter_L(LNode *p, ElemType &e);
void ListTraverse_L(LinkList L, Status(*visit)(ElemType e));
//創(chuàng)建包含n個元素的鏈表L，元素值存儲在data數(shù)組中
Status create(LinkList &L, ElemType *data, int n) {
? ? LNode *p, *q;
? ? int i;
? ? if (n < 0) return ERROR;
? ? L = NULL;
? ? p = L;
? ? for (i = 0; i < n; i++)
? ? {
? ? ? ? q = (LNode *)malloc(sizeof(LNode));
? ? ? ? if (NULL == q) return OVERFLOW;
? ? ? ? q->data = data[i];
? ? ? ? q->next = NULL;
? ? ? ? if (NULL == p) L = q;
? ? ? ? else p->next = q;
? ? ? ? p = q;
? ? }
? ? return OK;
}
//e從鏈表末尾入鏈表
Status EnQueue_LQ(LinkList &L, ElemType &e) {
? ? LinkList p, q;
? ? if (NULL == (q = (LNode *)malloc(sizeof(LNode)))) return OVERFLOW;
? ? q->data = e;
? ? q->next = NULL;
? ? if (NULL == L) L = q;
? ? else
? ? {
? ? ? ? p = L;
? ? ? ? while (p->next != NULL)
? ? ? ? {
? ? ? ? ? ? p = p->next;
? ? ? ? }
? ? ? ? p->next = q;
? ? }
? ? return OK;
}
//從鏈表頭節(jié)點(diǎn)出鏈表到e
Status DeQueue_LQ(LinkList &L, ElemType &e) {
? ? if (NULL == L) return ERROR;
? ? LinkList p;
? ? p = L;
? ? e = p->data;
? ? L = L->next;
? ? free(p);
? ? return OK;
}
//遍歷調(diào)用
Status visit(ElemType e) {
? ? printf("%d\t", e);
}
//遍歷單鏈表
void ListTraverse_L(LinkList L, Status(*visit)(ElemType e))
{
? ? if (NULL == L) return;
? ? for (LinkList p = L; NULL != p; p = p -> next) {
? ? ? ? visit(p -> data);
? ? }
}
int main() {
? ? int i;
? ? ElemType e, data[LONGTH] = { 1, 2, 3, 4, 5 };
? ? LinkList L;
? ? //顯示測試值
? ? printf("---【單鏈表】---\n");
? ? printf("待測試元素為：\n");
? ? for (i = 0; i < LONGTH; i++) printf("%d\t", data[i]);
? ? printf("\n");
? ? //創(chuàng)建鏈表L
? ? printf("創(chuàng)建鏈表L\n");
? ? if (ERROR == create(L, data, LONGTH))
? ? {
? ? ? ? printf("創(chuàng)建鏈表L失敗\n");
? ? ? ? return -1;
? ? }
? ? printf("成功創(chuàng)建包含%d個元素的鏈表L\n元素值存儲在data數(shù)組中\(zhòng)n", LONGTH);
? ? //遍歷單鏈表
? ? printf("此時鏈表中元素為：\n");
? ? ListTraverse_L(L, visit);
? ? //從鏈表頭節(jié)點(diǎn)出鏈表到e
? ? printf("\n出鏈表到e\n");
? ? DeQueue_LQ(L, e);
? ? printf("出鏈表的元素為：%d\n", e);
? ? printf("此時鏈表中元素為：\n");
? ? //遍歷單鏈表
? ? ListTraverse_L(L, visit);
? ? //e從鏈表末尾入鏈表
? ? printf("\ne入鏈表\n");
? ? EnQueue_LQ(L, e);
? ? printf("入鏈表的元素為：%d\n", e);
? ? printf("此時鏈表中元素為：\n");
? ? //遍歷單鏈表
? ? ListTraverse_L(L, visit);
? ? printf("\n");
? ? return 0;
}
/**
* @author huihut
* @E-mail:huihut@outlook.com
* @version 創(chuàng)建時間：2016年9月23日
* 說明：本程序?qū)崿F(xiàn)了一個具有頭結(jié)點(diǎn)的單鏈表。
*/
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
//5個常量定義
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
//類型定義
typedef int Status;
typedef int ElemType;
//測試程序長度定義
#define LONGTH 5
//鏈表的類型
typedef struct LNode {
? ? ElemType data;
? ? struct LNode *next;
} LNode, *LinkList;
Status InitList_L(LinkList &L);
Status DestroyList_L(LinkList &L);
Status ClearList_L(LinkList &L);
Status ListEmpty_L(LinkList L);
int ListLength_L(LinkList L);
LNode* Search_L(LinkList L, ElemType e);
LNode* NextElem_L(LNode *p);
Status InsertAfter_L(LNode *p, LNode *q);
Status DeleteAfter_L(LNode *p, ElemType &e);
void ListTraverse_L(LinkList L, Status(*visit)(ElemType e));
//創(chuàng)建包含n個元素的鏈表L，元素值存儲在data數(shù)組中
Status create(LinkList &L, ElemType *data, int n) {
? ? LNode *p, *q;
? ? int i;
? ? if (n < 0) return ERROR;? ?
? ? p = L = NULL;
? ? q = (LNode *)malloc(sizeof(LNode));
? ? if (NULL == q) return OVERFLOW;?
? ? q->next = NULL;
? ? p = L = q;
? ? for (i = 0; i < n; i++)
? ? {
? ? ? ? q = (LNode *)malloc(sizeof(LNode));
? ? ? ? if (NULL == q) return OVERFLOW;
? ? ? ? q->data = data[i];
? ? ? ? q->next = NULL;? ? ?
? ? ? ? p->next = q;
? ? ? ? p = q;
? ? }
? ? return OK;
}
//e從鏈表末尾入鏈表
Status EnQueue_LQ(LinkList &L, ElemType &e) {
? ? LinkList p, q;
? ? if (NULL == (q = (LNode *)malloc(sizeof(LNode)))) return OVERFLOW;
? ? q->data = e;
? ? q->next = NULL;
? ? if (NULL == L)
? ? {
? ? ? ? L = (LNode *)malloc(sizeof(LNode));
? ? ? ? if (NULL == L) return OVERFLOW;
? ? ? ? L -> next = q;
? ? }
? ? else if (NULL == L->next) L = q;
? ? else
? ? {
? ? ? ? p = L;
? ? ? ? while (p->next != NULL)
? ? ? ? {
? ? ? ? ? ? p = p->next;
? ? ? ? }
? ? ? ? p->next = q;
? ? }
? ? return OK;
}
//從鏈表頭節(jié)點(diǎn)出鏈表到e
Status DeQueue_LQ(LinkList &L, ElemType &e) {
? ? if (NULL == L || NULL == L->next) return ERROR;
? ? LinkList p;
? ? p = L->next;
? ? e = p->data;
? ? L->next = p->next;
? ? free(p);
? ? return OK;
}
//遍歷調(diào)用
Status visit(ElemType e) {
? ? printf("%d\t", e);
}
//遍歷單鏈表
void ListTraverse_L(LinkList L, Status(*visit)(ElemType e))
{
? ? if (NULL == L || NULL == L->next) return;
? ? for (LinkList p = L -> next; NULL != p; p = p -> next) {
? ? ? ? visit(p -> data);
? ? }
}
int main() {
? ? int i;
? ? ElemType e, data[LONGTH] = { 1, 2, 3, 4, 5 };
? ? LinkList L;
? ? //顯示測試值
? ? printf("---【有頭結(jié)點(diǎn)的單鏈表】---\n");
? ? printf("待測試元素為：\n");
? ? for (i = 0; i < LONGTH; i++) printf("%d\t", data[i]);
? ? printf("\n");
? ? //創(chuàng)建鏈表L
? ? printf("創(chuàng)建鏈表L\n");
? ? if (ERROR == create(L, data, LONGTH))
? ? {
? ? ? ? printf("創(chuàng)建鏈表L失敗\n");
? ? ? ? return -1;
? ? }
? ? printf("成功創(chuàng)建包含1個頭結(jié)點(diǎn)、%d個元素的鏈表L\n元素值存儲在data數(shù)組中\(zhòng)n", LONGTH);
? ? //遍歷單鏈表
? ? printf("此時鏈表中元素為：\n");
? ? ListTraverse_L(L, visit);
? ? //從鏈表頭節(jié)點(diǎn)出鏈表到e
? ? printf("\n出鏈表到e\n");
? ? DeQueue_LQ(L, e);
? ? printf("出鏈表的元素為：%d\n", e);
? ? printf("此時鏈表中元素為：\n");
? ? //遍歷單鏈表
? ? ListTraverse_L(L, visit);
? ? //e從鏈表末尾入鏈表
? ? printf("\ne入鏈表\n");
? ? EnQueue_LQ(L, e);
? ? printf("入鏈表的元素為：%d\n", e);
? ? printf("此時鏈表中元素為：\n");
? ? //遍歷單鏈表
? ? ListTraverse_L(L, visit);
? ? printf("\n");
? ? return 0;
}
/**
* @author huihut
* @E-mail:huihut@outlook.com
* @version 創(chuàng)建時間：2016年9月9日
* 說明：本程序?qū)崿F(xiàn)了一個順序表。
*/
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
//5個常量定義
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
//測試程序長度定義
#define LONGTH 5
//類型定義
typedef int Status;
typedef int ElemType;
//順序棧的類型
typedef struct {
? ? ElemType *elem;
? ? int length;
? ? int size;
? ? int increment;
} SqList;
Status InitList_Sq(SqList &L, int size, int inc);? ? //初始化順序表L
Status DestroyList_Sq(SqList &L);? ? ? ? ? ? ? ? ? ? //銷毀順序表L
Status ClearList_Sq(SqList &L);? ? ? ? ? ? ? ? ? ? ? ? //將順序表L清空
Status ListEmpty_Sq(SqList L);? ? ? ? ? ? ? ? ? ? ? ? //若順序表L為空表，則返回TRUE，否則FALSE
int ListLength_Sq(SqList L);? ? ? ? ? ? ? ? ? ? ? ? //返回順序表L中元素個數(shù)
Status GetElem_Sq(SqList L, int i, ElemType &e);? ? //用e返回順序表L中第i個元素的值
int Search_Sq(SqList L, ElemType e);? ? ? ? ? ? ? ? //在順序表L順序查找元素e，成功時返回該元素在表中第一次出現(xiàn)的位置，否則返回-1
Status ListTraverse_Sq(SqList L, Status(*visit)(ElemType e));? ? //遍歷順序表L，依次對每個元素調(diào)用函數(shù)visit()
Status PutElem_Sq(SqList &L, int i, ElemType e);? ? //將順序表L中第i個元素賦值為e
Status Append_Sq(SqList &L, ElemType e);? ? ? ? ? ? //在順序表L表尾添加元素e
Status DeleteLast_Sq(SqList &L, ElemType &e);? ? ? ? //刪除順序表L的表尾元素，并用參數(shù)e返回其值
//初始化順序表L
Status InitList_Sq(SqList &L, int size, int inc) {
? ? L.elem = (ElemType *)malloc(size * sizeof(ElemType));
? ? if (NULL == L.elem) return OVERFLOW;
? ? L.length = 0;
? ? L.size = size;
? ? L.increment = inc;
? ? return OK;
}
//銷毀順序表L
Status DestroyList_Sq(SqList &L) {
? ? free(L.elem);
? ? L.elem = NULL;
? ? return OK;
}
//將順序表L清空
Status ClearList_Sq(SqList &L) {
? ? if (0 != L.length) L.length = 0;
? ? return OK;
}
//若順序表L為空表，則返回TRUE，否則FALSE
Status ListEmpty_Sq(SqList L) {
? ? if (0 == L.length) return TRUE;
? ? return FALSE;
}
//返回順序表L中元素個數(shù)
int ListLength_Sq(SqList L) {
? ? return L.length;
}
// 用e返回順序表L中第i個元素的值
Status GetElem_Sq(SqList L, int i, ElemType &e) {
? ? e = L.elem[--i];
? ? return OK;
}
// 在順序表L順序查找元素e，成功時返回該元素在表中第一次出現(xiàn)的位置，否則返回 - 1
int Search_Sq(SqList L, ElemType e) {
? ? int i = 0;
? ? while (i < L.length && L.elem[i] != e) i++;
? ? if (i < L.length) return i;
? ? else return -1;
}
//遍歷調(diào)用
Status visit(ElemType e) {
? ? printf("%d\t",e);
}
//遍歷順序表L，依次對每個元素調(diào)用函數(shù)visit()
Status ListTraverse_Sq(SqList L, Status(*visit)(ElemType e)) {
? ? if (0 == L.length) return ERROR;
? ? for (int i = 0; i < L.length; i++) {
? ? ? ? visit(L.elem[i]);
? ? }
? ? return OK;
}
//將順序表L中第i個元素賦值為e
Status PutElem_Sq(SqList &L, int i, ElemType e) {
? ? if (i > L.length) return ERROR;
? ? e = L.elem[--i];
? ? return OK;
}
//在順序表L表尾添加元素e
Status Append_Sq(SqList &L, ElemType e) {
? ? if (L.length >= L.size) return ERROR;
? ? L.elem[L.length] = e;
? ? L.length++;
? ? return OK;
}
//刪除順序表L的表尾元素，并用參數(shù)e返回其值
Status DeleteLast_Sq(SqList &L, ElemType &e) {
? ? if (0 == L.length) return ERROR;
? ? e = L.elem[L.length - 1];
? ? L.length--;
? ? return OK;
}
int main() {
? ? //定義表L
? ? SqList L;
? ? //定義測量值
? ? int size, increment, i;
? ? //初始化測試值
? ? size = LONGTH;
? ? increment = LONGTH;
? ? ElemType e, eArray[LONGTH] = { 1, 2, 3, 4, 5 };
? ? //顯示測試值
? ? printf("---【順序?！?--\n");
? ? printf("表L的size為：%d\n表L的increment為：%d\n", size, increment);
? ? printf("待測試元素為：\n");
? ? for (i = 0; i < LONGTH; i++) {
? ? ? ? printf("%d\t", eArray[i]);
? ? }
? ? printf("\n");
? ? //初始化順序表
? ? if (!InitList_Sq(L, size, increment)) {
? ? ? ? printf("初始化順序表失敗\n");
? ? ? ? exit(0);
? ? }
? ? printf("已初始化順序表\n");
? ? //判空
? ? if(TRUE == ListEmpty_Sq(L)) printf("此表為空表\n");
? ? else printf("此表不是空表\n");
? ? //入表
? ? printf("將待測元素入表：\n");
? ? for (i = 0; i < LONGTH; i++) {
? ? ? ? if(ERROR == Append_Sq(L, eArray[i])) printf("入表失敗\n");;
? ? }
? ? printf("入表成功\n");
? ? //遍歷順序表L
? ? printf("此時表內(nèi)元素為：\n");
? ? ListTraverse_Sq(L, visit);
? ? //出表
? ? printf("\n將表尾元素入表到e：\n");
? ? if (ERROR == DeleteLast_Sq(L, e)) printf("出表失敗\n");
? ? printf("出表成功\n出表元素為%d\n",e);
? ? //遍歷順序表L
? ? printf("此時表內(nèi)元素為：\n");
? ? ListTraverse_Sq(L, visit);
? ? //銷毀順序表
? ? printf("\n銷毀順序表\n");
? ? if(OK == DestroyList_Sq(L)) printf("銷毀成功\n");
? ? else printf("銷毀失敗\n");
? ? return 0;
}
/**
* @author huihut
* @E-mail:huihut@outlook.com
* @version 創(chuàng)建時間：2016年9月9日
* 說明：本程序?qū)崿F(xiàn)了一個順序棧。
* 功能：有初始化、銷毀、判斷空、清空、入棧、出棧、取元素的操作。
*/
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
//5個常量定義
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
//測試程序長度定義
#define LONGTH 5
//類型定義
typedef int Status;
typedef int ElemType;
//順序棧的類型
typedef struct {
? ? ElemType *elem;
? ? int top;
? ? int size;
? ? int increment;
} SqSrack;
//函數(shù)聲明
Status InitStack_Sq(SqSrack &S, int size, int inc);? //初始化順序棧
Status DestroyStack_Sq(SqSrack &S);? ? ? ? ? ? ? ? ? ? //銷毀順序棧
Status StackEmpty_Sq(SqSrack S);? ? ? ? ? ? ? ? ? ? //判斷S是否空，若空則返回TRUE，否則返回FALSE
void ClearStack_Sq(SqSrack &S);? ? ? ? ? ? ? ? ? ? ? ? //清空棧S
Status Push_Sq(SqSrack &S, ElemType e);? ? ? ? ? ? ? ? //元素e壓入棧S
Status Pop_Sq(SqSrack &S, ElemType &e);? ? ? ? ? ? ? ? //棧S的棧頂元素出棧，并用e返回
Status GetTop_Sq(SqSrack S, ElemType &e);? ? ? ? ? ? //取棧S的棧頂元素，并用e返回
//初始化順序棧
Status InitStack_Sq(SqSrack &S, int size, int inc) {
? ? S.elem = (ElemType *)malloc(size * sizeof(ElemType));
? ? if (NULL == S.elem) return OVERFLOW;
? ? S.top = 0;
? ? S.size = size;
? ? S.increment = inc;
? ? return OK;
}
//銷毀順序棧
Status DestroyStack_Sq(SqSrack &S) {
? ? free(S.elem);
? ? S.elem = NULL;
? ? return OK;
}
//判斷S是否空，若空則返回TRUE，否則返回FALSE
Status StackEmpty_Sq(SqSrack S) {
? ? if (0 == S.top) return TRUE;
? ? return FALSE;
}
//清空棧S
void ClearStack_Sq(SqSrack &S) {
? ? if (0 == S.top) return;
? ? S.size = 0;
? ? S.top = 0;
}
//元素e壓入棧S
Status Push_Sq(SqSrack &S, ElemType e) {
? ? ElemType *newbase;
? ? if (S.top >= S.size) {
? ? ? ? newbase = (ElemType *)realloc(S.elem, (S.size + S.increment) * sizeof(ElemType));
? ? ? ? if (NULL == newbase) return OVERFLOW;
? ? ? ? S.elem = newbase;
? ? ? ? S.size += S.increment;
? ? }
? ? S.elem[S.top++] = e;
? ? return OK;
}
//取棧S的棧頂元素，并用e返回
Status GetTop_Sq(SqSrack S, ElemType &e) {
? ? if (0 == S.top) return ERROR;
? ? e = S.elem[S.top - 1];
? ? return e;
}
//棧S的棧頂元素出棧，并用e返回
Status Pop_Sq(SqSrack &S, ElemType &e) {
? ? if (0 == S.top) return ERROR;
? ? e = S.elem[S.top - 1];
? ? S.top--;
? ? return e;
}
int main() {
? ? //定義棧S
? ? SqSrack S;
? ? //定義測量值
? ? int size, increment, i;
? ? //初始化測試值
? ? size = LONGTH;
? ? increment = LONGTH;
? ? ElemType e, eArray[LONGTH] = { 1, 2, 3, 4, 5 };
? ? //顯示測試值
? ? printf("---【順序棧】---\n");
? ? printf("棧S的size為：%d\n棧S的increment為：%d\n", size, increment);
? ? printf("待測試元素為：\n");
? ? for (i = 0; i < LONGTH; i++) {
? ? ? ? printf("%d\t", eArray[i]);
? ? }
? ? printf("\n");
? ? //初始化順序棧
? ? if (!InitStack_Sq(S, size, increment)) {
? ? ? ? printf("初始化順序棧失敗\n");
? ? ? ? exit(0);
? ? }
? ? printf("已初始化順序棧\n");
? ? //入棧
? ? for (i = 0; i < S.size; i++) {
? ? ? ? if (!Push_Sq(S, eArray[i])) {
? ? ? ? ? ? printf("%d入棧失敗\n", eArray[i]);
? ? ? ? ? ? exit(0);
? ? ? ? }
? ? }
? ? printf("已入棧\n");
? ? //判斷非空
? ? if(StackEmpty_Sq(S)) printf("S棧為空\n");
? ? else printf("S棧非空\n");
? ? //取棧S的棧頂元素? ?
? ? printf("棧S的棧頂元素為：\n");
? ? printf("%d\n", GetTop_Sq(S, e));? ?
? ? //棧S元素出棧
? ? printf("棧S元素出棧為：\n");
? ? for (i = 0, e = 0; i < S.size; i++) {
? ? ? ? printf("%d\t", Pop_Sq(S, e));
? ? }?
? ? printf("\n");
? ? //清空棧S
? ? ClearStack_Sq(S);
? ? printf("已清空棧S\n");
? ? return 0;? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
}
