Question

c语言编程 数据结构题

创建线性链式表并在链式表创建节点，节点的值为{1，4，6，7，10}，然后在查找数据为6的节点的位置在6节点之前插入5打印输出，然后删除值为7的元素并打印输出。
拜托了！

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define elemType int							/* 单链表元素数据类型 */
#define LNODE_SIZE sizeof (struct lNode)		/* 单链表结点空间大小 */

#define status int	/* 状态型变量 */
#define OVERFLOW -1	/* 内存溢出状态码 */
#define ERROR 0		/* 错误状态码 */
#define OK 1		/* 正确状态码 */

/* 单链表数据结构 */
typedef struct lNode {
	elemType data;
	struct lNode *next;
} lNode, *linkList;

/* 初始化 */
/* 操作结果：构造一个空的单链表L */
void initList (linkList *L) {
	*L = (linkList) malloc (LNODE_SIZE); /* 产生头结点，并使L指向此头结点 */
	if(!*L) /* 内存分配失败 */
		exit (OVERFLOW);
	(*L)->next = NULL; /* 指针域为空 */
}

/* 销毁 */
/* 初始条件：单链表L已存在。操作结果：销毁单链表L */
void destroyList (linkList L) {
	linkList p,q;
	
	p = L->next; /* p指向第一个结点 */
	while (p) { /* 没到表尾 */
		q = p->next;
    	free (p);
    	p = q;
	}
	free (L);
}

/* 判断单链表是否为空 */
/* 初始条件：单链表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
int listIsEmpty (linkList L) {
	return L->next == NULL;
}

/* 寻找指定特征(compare)元素的位序 */
/* 初始条件: 线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0) */
/* 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序 */
/* 若这样的数据元素不存在，则返回值为0 */
int locateElem (linkList L, elemType e, status(*compare)(elemType, elemType)) {
	int i = 0;
    linkList p = L->next;
    while (p) {
        i++;
        if (compare(p->data, e)) /*找到这样的数据元素*/
            return i;
        p = p->next;
    }
    return 0;
}

/* 数据元素判定 */
/* 满足为1，否则为0 */
int compare (elemType des, elemType src) {
	return des==src;
}

/* 单链表指定位置插入新元素 */
/* 操作结果：在带头结点的单链表L中第i个位置之前插入元素e */
status listInsertNode (linkList L, int i, elemType e) {
	int j=0;
	linkList p=L,s;
	
	while (p && j<i-1) { /* 寻找第i-1个结点 */
		p = p->next;
    	j++;
	}
	
	if (!p || j>i-1) /* 插入位置不合理：i小于1或者大于表长 */
		return ERROR;
	
	/* 生成新结点，并插入L中 */
	s = (linkList) malloc (LNODE_SIZE);
	if(!s) /* 内存分配失败 */
		exit (OVERFLOW);
	s->data = e;
	s->next = p->next;
	p->next = s;
	
	return OK;
}

/* 删除单链表指定位置元素 */
/* 操作结果：在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 */
status listDeleteNode (linkList L, int i, elemType *e) {
	int j = 0;
	linkList p = L, q;
	
	while (p->next && j<i-1) { /* 寻找第i个结点，并令p指向其前驱结点 */
    	p = p->next;
		j++;
	}
	
	if (!p->next || j>i-1) /* 删除位置不合理：i小于1或者大于表长 */
		return ERROR;
	
	/* 删除并释放结点 */
	q = p->next;
	p->next = q->next;
	*e = q->data;
	free (q);
	
	return OK;
}

/* 打印链表内容 */
/* 初始条件：单链表L已存在。操作结果：当链表不为空时，打印链表内容并返回OK，否则返回ERROR */
status printList (linkList L) {
	linkList p = L->next; /* p指向第一个结点 */
	
	if (listIsEmpty (L)) {
		puts ("The link list is empty! ");
		return ERROR;
	}
	
	while (p) {
		printf ("%d\t", p->data);
		p = p->next;
	}
	putchar ('\n');
	return OK;
}

int main (void) {
	linkList L;
	elemType e;
	int index;
	
	/* 初始化链表 */
	initList (&L);
	/* 插入若干元素 */
	listInsertNode (L, 1, 1);
	listInsertNode (L, 2, 4);
	listInsertNode (L, 3, 6);
	listInsertNode (L, 4, 7);
	listInsertNode (L, 5, 10);
	
	printf ("初始链表内容：\n");
	printList (L);
	putchar ('\n');
	
	/* 寻找数据为6的结点位置 */ 
	index = locateElem (L, 6, &compare);
	printf ("数据为6的结点位置：\n%d\n", index);
	putchar ('\n');
	
	/* 在数据为6的结点之前插入数据为5的结点 */ 
	listInsertNode (L, index, 5);
	
	printf ("当前链表内容：\n");
	printList (L);
	
	destroyList (L); 
	
	getch (); /* 屏幕暂留 */ 
	return 0 ;
}

Answer 2

这是单链表最基础的操作，包括创建，插入，删除，遍历，插入分头插和尾插，删除的时候要把删掉节点的内存free掉。