浏览 2712 次
锁定老帖子 主题:c语言单链表增删查
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2009-05-26
#ifndef _LINKLIST_H_ #define _LINKLIST_H_ #include <stdio.h> #include <stdlib.h> #include <windows.h> #include <time.h> typedef unsigned char DataType; typedef struct NODE { DataType c; struct NODE* next; } LinkNode; LinkNode* CreateLink(DataType* pCh); LinkNode* FindLinkE(LinkNode* head, int nPos); void InsertLinkE(LinkNode* head, int nPos, DataType insertData); void DeleteLinkE(LinkNode* head, int nPos); void FindData(LinkNode* head, DataType ch); void InitData(LinkNode arrNode[], DataType* cData, int arrLen); void CompareEffic(DataType* pCh, DataType ch); #endif /* 创建结点 */ LinkNode* CreateLink(DataType* pCh) { typedef LinkNode* linkList; LinkNode* head = NULL; //头指针 linkList p1,p2; //p1是中间指针,p2是尾指针 while(*pCh != 0) { p1 = (linkList)malloc(sizeof(LinkNode)); p1->c = *pCh; if(NULL == head) { head = p1; }else { p2->next = p1; } p1->next = NULL; p2 = p1; ++pCh; } return head; } /* 查找结点 */ LinkNode* FindLinkE(LinkNode* head, int nPos) { int i = 0; while(head->next && i < nPos) { head = head->next; ++i; } if(i == nPos)//此时找到要找的结点 { return head; } return NULL; } /* 插入结点 */ void InsertLinkE(LinkNode* head, int nPos, DataType insertData) { int i = 0; LinkNode* p1 = NULL; p1 = FindLinkE(head, nPos - 1);//找到插入当前结点的上个结点 if(NULL == p1) { printf("对不起,操作有误!\n"); Sleep(2000); throw "无效的数据"; } //生成插入的结点 LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode)); //初始化当前结点 s->c = insertData; s->next = p1->next;//将s成员中的next指向将p1的后一个结点 p1->next = s; } /* 删除结点 */ void DeleteLinkE(LinkNode* head, int nPos) { //找到删除结点 LinkNode* delNode = FindLinkE(head, nPos); if(NULL == delNode) { printf("操作有误\n"); exit(1); } //找到删除结点的上一个结点 if(nPos < 1) return; LinkNode* p1 = FindLinkE(head, nPos - 1); if(NULL != p1) { p1->next = delNode->next; } free(delNode);//必须释放 } /* 比较一下数组查找和链表查找效率问题 相同数据 */ void CompareEffic(DataType* pCh, DataType ch) { LinkNode arrNode[1000] = {0}; LinkNode* head = CreateLink(pCh); InitData(arrNode, pCh, 255); //查找链表 time_t t_link1 = time(NULL); tm* tm_link1 = localtime(&t_link1); int mill1 = tm_link1->tm_sec * 1000; FindData(head, ch);//查找元素位于结点上 time_t t_link2 = time(NULL); tm* tm_link2 = localtime(&t_link2); int mill2 = tm_link2->tm_sec * 1000; //时间之差 int link_result = mill2 - mill1; //查找数组 time_t t_array1 = time(NULL); tm* tm_array1 = localtime(&t_array1); int millarray1 = tm_array1->tm_sec * 1000; for(int i = 0;i < 1000;++i) { if(arrNode[i].c == ch) { break; } } time_t t_array2 = time(NULL); tm* tm_array2 = localtime(&t_array2); int millarray2 = tm_array2->tm_sec * 1000; //时间之差 int arr_result = millarray2 - millarray1; if(arr_result < link_result) { printf("数组查找速率快\n"); }else { printf("数据太少,无法检测两者差异!\n"); } } /* 初始化数组数据 */ void InitData(LinkNode arrNode[], DataType* cData, int arrLen) { int nCnt = 0; while(*cData != 0) { if(nCnt > arrLen - 1) break; arrNode->c = *cData; ++cData; ++nCnt; } } /* 查找指定数据 */ void FindData(LinkNode* head, DataType ch) { if(NULL == head) return; int i = 0; while(head->next != NULL) { if(head->c == ch) { printf("查找到%c在当前结点位置%d\n", ch, i); break; } head = head->next; ++i; } } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |