双向链表的基本操作代码,C代码库,德仔网

代码语言
代码分类
【C】双向链表的基本操作
作者:天远 / 发布于2015/8/3/ 968
VC2010 环境下的双向链表基本操作，包括内存申请，释放，查找，删除，插入，排序等

	#include "stdafx.h"
	#include "stdlib.h"
	#include "string.h"
	#include "cstdlib"
	#include "time.h"
	#include "windows.h"
	#define OK 0
	#define NG -1
	enum
	{
	 CREAT = 1,
	 FREE,
	 SEARCH,
	 INSERT,
	 DEL,
	 SORT
	};
	
	typedef struct ltbl
	{
	struct ltbl* pPre; /* 指向链表中前一个元素的指针 */
	struct ltbl* pNxt; /* 指向链表中后一个元素的指针 */
	int nKey; /* KEY VALUE */
	unsigned char ucDummy[32]; /* 备用 */
	}LTBL;
	
	typedef struct mng
	{
	int nNodeCnt; /* 链表的长度 */
	LTBL* pHead; /* 指向链表头的指针 */
	}MNG;
	2. [代码]程序代码
	?
	1
	2
	3
	4
	5
	6
	7
	8
	9
	10
	11
	12
	13
	14
	15
	16
	17
	18
	19
	20
	21
	22
	23
	24
	25
	26
	27
	28
	29
	30
	31
	32
	33
	34
	35
	36
	37
	38
	39
	40
	41
	42
	43
	44
	45
	46
	47
	48
	49
	50
	51
	52
	53
	54
	55
	56
	57
	58
	59
	60
	61
	62
	63
	64
	65
	66
	67
	68
	69
	70
	71
	72
	73
	74
	75
	76
	77
	78
	79
	80
	81
	82
	83
	84
	85
	86
	87
	88
	89
	90
	91
	92
	93
	94
	95
	96
	97
	98
	99
	100
	101
	102
	103
	104
	105
	106
	107
	108
	109
	110
	111
	112
	113
	114
	115
	116
	117
	118
	119
	120
	121
	122
	123
	124
	125
	126
	127
	128
	129
	130
	131
	132
	133
	134
	135
	136
	137
	138
	139
	140
	141
	142
	143
	144
	145
	146
	147
	148
	149
	150
	151
	152
	153
	154
	155
	156
	157
	158
	159
	160
	161
	162
	163
	164
	165
	166
	167
	168
	169
	170
	171
	172
	173
	174
	175
	176
	177
	178
	179
	180
	181
	182
	183
	184
	185
	186
	187
	188
	189
	190
	191
	192
	193
	194
	195
	196
	197
	198
	199
	200
	201
	202
	203
	204
	205
	206
	207
	208
	209
	210
	211
	212
	213
	214
	215
	216
	217
	218
	219
	220
	221
	222
	223
	224
	225
	226
	227
	228
	229
	230
	231
	232
	233
	234
	235
	236
	237
	238
	239
	240
	241
	242
	243
	244
	245
	246
	247
	248
	249
	250
	251
	252
	253
	254
	255
	256
	257
	258
	259
	260
	261
	262
	263
	264
	265
	266
	267
	268
	269
	270
	271
	272
	273
	274
	275
	276
	277
	278
	279
	280
	281
	282
	283
	284
	285
	286
	287
	288
	289
	290
	291
	292
	293
	294
	#include "stdafx.h"
	#include "List.h"
	
	/*List creation function*/
	int TBLCreate (MNG *pMng, int nCnt)
	{
	 LTBL *P, *L;
	 pMng->pHead = (LTBL *)malloc(sizeof(LTBL) );
	
	 if(NULL == pMng->pHead)
	 {
	 printf("Memory is error!");
	 return NG;
	 }
	
	 L = pMng->pHead;
	 L->pPre = NULL;
	 srand(time(NULL) );
	
	 for(int i = 0; i < nCnt; ++i)
	 {
	 P = (LTBL *)malloc(sizeof(LTBL) );
	
	 if(NULL == P)
	 {
	 printf("Memory is error!");
	 return NG;
	 }
	
	 P->nKey = rand() % 100 + 1;
	 L->nKey = rand() % 100 + 1;
	 L->pNxt = P;
	 P->pPre = L;
	 L = L->pNxt;
	 }
	
	 P->pNxt = NULL;
	 pMng->nNodeCnt = nCnt;
	 return OK;
	}
	
	/*Release function of linked list memory space*/
	void TBLFree (MNG* pMng)
	{
	 free (pMng->pHead);
	 pMng->pHead = NULL;
	 pMng->nNodeCnt = 0;
	 printf("Successfully released list\n");
	}
	
	/*Search function of element address in list*/
	LTBL* TBLSearch (const MNG* pMng, int nKey)
	{
	 LTBL *LL;
	 LL = pMng->pHead;
	
	 for(int i = 0; i < pMng->nNodeCnt; ++i)
	 {
	
	 if(nKey == LL->nKey)
	 {
	 return LL ;
	 }
	
	 else
	 {
	 LL = LL->pNxt;
	 }
	 }
	
	 return NULL;
	}
	
	/*Sort function of list elements*/
	void TBLSort(MNG *pMng, int nFlg)
	{
	 bool change = 1;
	 for (int i = pMng->nNodeCnt-1; i >= 1 && change; --i)
	 {
	 LTBL *aa = pMng->pHead, *bb = pMng->pHead;
	 change = 0;
	 for(int j = 0; j<i; ++j)
	 {
	 aa = bb;
	 while(NULL != bb->pNxt)
	 {
	 bb = bb->pNxt;
	 break;
	 }
	 if(1 == nFlg)
	 {
	 if( aa->nKey > bb->nKey)
	 {
	 int temp;
	 temp = aa->nKey;
	 aa->nKey = bb->nKey;
	 bb->nKey = temp;
	 change = 1;
	 }
	 }
	 else
	 {
	 if(aa->nKey < bb->nKey)
	 {
	 int temp;
	 temp = aa->nKey;
	 aa->nKey = bb->nKey;
	 bb->nKey = temp;
	 change = 1;
	 }
	 }
	 }
	 }
	}
	
	/*Insertion function of linked list elements*/
	int TBLInsert(MNG* pMng, LTBL* pNode)
	{
	 TBLSort(pMng,1);
	 LTBL *P = pMng->pHead;
	 for(int i = 0; i < pMng->nNodeCnt; ++i)
	 {
	 if(P->nKey < pNode->nKey )
	 {
	 P = P->pNxt;
	 continue;
	 }
	 else if(P->pPre != NULL && P->pNxt !=NULL)
	 {
	 if( P->nKey == pNode->nKey)
	 {
	 printf("Insert is error!\n");
	 return NG;
	 }
	 pNode->pPre = P->pPre;
	 P->pPre->pNxt = pNode;
	 pNode->pNxt = P;
	 P->pPre = pNode;
	 ++pMng->nNodeCnt;
	 return OK;
	 }
	 else if(P->pPre == NULL)
	 {
	 pNode->pPre = NULL;
	 pNode->pNxt = P;
	 P->pPre = pNode;
	 pMng->pHead = pNode;
	 ++pMng->nNodeCnt;
	 return OK;
	 }
	 else if(P->pNxt == NULL)
	 {
	 pNode->pNxt = NULL;
	 pNode->pPre = P;
	 P->pNxt = pNode;
	 ++pMng->nNodeCnt;
	 return OK;
	 }
	
	 }
	}
	
	/*Delete function of the elements in the list*/
	int TBLDelete(MNG* pMng, int nKey)
	{
	 LTBL *P;
	 P = TBLSearch(pMng,nKey);
	 if(NULL == P)
	 {
	 printf("Delete is error!\n");
	 return NG;
	 }
	 P->pPre->pNxt = P->pNxt;
	 P->pNxt->pPre = P->pPre;
	 free(P);
	 return OK;
	}
	
	/*Print list element values*/
	void Print(LTBL *LL)
	{
	 while(LL->pNxt != NULL)
	 {
	 printf("%d ", LL ->nKey);
	 LL = LL->pNxt;
	 }
	 putchar('\n');
	}
	
	/*Select the value of the specified position in the linked list*/
	int Choice(MNG *pMng, int num)
	{
	 LTBL * LL=pMng->pHead ;
	 while(num > pMng->nNodeCnt )
	 {
	 printf("Intput is error,Please input again!");
	 scanf("%d", &num);
	 }
	 for(int i=0; i < num-1; ++i)
	 {
	 LL = LL->pNxt ;
	 }
	 return LL->nKey ;
	}
	
	int _tmain(int argc, _TCHAR* argv[])
	{
	
	 int nFlg = 0, vs = 1,work = 1,sign = 1, nKey = 1;
	 int num = 1;
	 MNG mng1, mng2;
	 MNG *pMng = &mng1;
	 MNG *pMng1 = &mng2;
	 LTBL *LL, *pNode, *kkk;
	 while(work)
	 {
	 system("cls");
	 printf(" Welcome To The LTBL Operation system! \n");
	 printf("------------------------------------------------\n");
	 printf("1: The list of the formation and the list of the initialization!\n");
	 printf("2: Release of linked list memory space!\n");
	 printf("3: Linked list search operation!\n");
	 printf("4: Insertion operation of linked list!\n");
	 printf("5: Delete list operation!\n");
	 printf("6: Sorting list!\n");
	 printf("------------------------------------------------\n");
	 printf("Please Select Operation Type:");
	 scanf("%d", &sign);
	 switch(sign)
	 {
	 case CREAT:
	 printf("Please enter the length of the linked list.\n");
	 scanf("%d", &vs);
	 TBLCreate(pMng, vs);
	 LL = pMng->pHead;
	 Print(LL);
	 break;
	 case FREE:
	 if(NULL == pMng)
	 {
	 printf("The linked list is null ,not free!\n");
	 break;
	 }
	 TBLFree(pMng);
	 break;
	 case SEARCH:
	 printf("Please enter the nKey in the linked list.\n");
	 scanf("%d", &num);
	 nKey = Choice(pMng,num) ;
	 kkk = TBLSearch (pMng, nKey);
	 printf("The %d is in %d address\n", nKey, kkk);
	 break;
	 case INSERT:
	 TBLCreate(pMng1, 1);
	 pNode = pMng1->pHead;
	 printf("The value of the generated node element is: %d\n", pNode->nKey);
	 printf("Insert node after the list is:\n");
	 TBLInsert(pMng, pNode);
	 LL = pMng->pHead;
	 Print(LL);
	 break;
	 case DEL:
	 printf("Please enter the nKey in the linked list.\n");
	 scanf("%d", &num);
	 nKey = Choice(pMng,num) ;
	 nKey = pMng->pHead->pNxt ->nKey;
	 TBLDelete(pMng, nKey);
	 LL = pMng->pHead;
	 Print(LL);
	 break;
	 case SORT:
	 printf("Please enter the list of the sorting method.\n");
	 scanf("%d", &nFlg);
	 TBLSort(pMng, nFlg);
	 LL = pMng->pHead;
	 Print(LL);
	 break;
	 default:
	 printf("Input is error!\n");
	 }
	 printf("Whether exit the linked list system?(1 is not exit,0 is exit)\n"); //whether exit the system.
	 scanf("%d", &work);
	 fflush(stdin);
	
	 while (work != 0 && work != 1) //work must is 1 or 0.
	 {
	 printf(" Input is error,Please input again!\n");
	 scanf("%d", &work);
	 fflush(stdin);
	 }
	 }
	 printf("\n-------------Thanks For You Using The Linked List System !--------------\n");
	 Sleep(2000); //delay some times.
	}
试试其它关键字
　双向链表　
同语言下
可能有用的
天远贡献的其它代码(16)