论坛首页 编程语言技术论坛

c语言单链表增删查

浏览 2712 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2009-05-26  
C
#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;
	}
}



论坛首页 编程语言技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics