关于实现多链表
我正在开发一个类似于地址簿的项目.首先,我们在一个文本文件中有许多学生.我将实现一个多链表,该列表有2个头+尾指针(头部+尾部指针,用于名称,姓氏).这些指针显示相同的列表但位置不同,因为我按升序添加节点并使用双指针向后打印列表.问题是我通过名称和姓氏添加节点来实现列表,当我插入另一个时,操作成功.但我意识到,当我用她/他的"名字"删除节点并再次打印列表时,学生不存在,但当我按"姓氏"打印列表时,学生确实存在.然后我认识到我实施了两个单独的链表.我被告知只实现一个添加和删除功能.但是,我如何通过其名字指针和姓氏指针一起添加节点？我希望我可以理解地解释我的问题.这是我的代码块.
我的结构:
typedef struct node {
int birth_date;
int zipcode;
int phone_num;
char first_name[50];
char last_name[50];
char city[50];
char address[50];
char email_addr[50];
struct node* fn_next;
struct node* fn_pre;
struct node* ln_next;
struct node* ln_pre;
struct node* birdat_next;
struct node* birdat_pre;
} NODE;
typedef struct {
int fn_count;
int ln_count;
NODE* fn_head;
NODE* ln_head;
NODE* fn_tail;
NODE* ln_tail;
}LIST;
代码块,我逐行读取文件并调用add函数:
while ( !feof(myfile) ) {
NODE* pnew_stu;
if( !(pnew_stu = (NODE*) malloc(sizeof(NODE))) ) {
printf("ERROR NOT ENOUGH MEMORY!!!\n");
exit(100);
}
fscanf(myfile,"%s", &(pnew_stu->first_name) );
fscanf(myfile,"%s", &(pnew_stu->last_name) );
fscanf(myfile,"%s", &(pnew_stu->email_addr) );
fscanf(myfile,"%d", &(pnew_stu->phone_num) );
fscanf(myfile,"%s", &(pnew_stu->address) );
fscanf(myfile,"%s", &(pnew_stu->city) );
fscanf(myfile,"%d", &(pnew_stu->zipcode) );
add_Node(list,pnew_stu);
}
最后我的添加功能:
void add_fn_Node(LIST* list, NODE* pnew_stu) {
NODE* temp = list->fn_head;
if( list->fn_head == NULL ) {
pnew_stu->fn_next = list->fn_head;
pnew_stu->fn_pre = list->fn_head;
list->fn_head = pnew_stu;
list->fn_count = 1;
return;
}
else {
if ( (strcmp( pnew_stu->first_name, temp->first_name )) <= 0 ) { // Basa Ekleme Kosulu
pnew_stu->fn_next = temp;
pnew_stu->fn_pre = temp->fn_pre;
temp->fn_pre = pnew_stu;
list->fn_head = pnew_stu;
list->fn_count++;
return;
}
else {
while ( temp->fn_next != NULL ) { // Ortaya Ekleme Kosulu
if ( (strcmp( pnew_stu->first_name, temp->first_name ) >= 0 ) && (strcmp( pnew_stu->first_name, temp->fn_next->first_name) < 0)) {
pnew_stu->fn_next = temp->fn_next;
pnew_stu->fn_pre = temp;
temp->fn_next->fn_pre = pnew_stu;
temp->fn_next = pnew_stu;
list->fn_count++;
return;
}
temp = temp->fn_next;
}
if ( temp->fn_next == NULL ) { // Sona Ekleme Kosulu
temp->fn_next = pnew_stu;
pnew_stu->fn_pre = temp;
pnew_stu->fn_next = NULL;
list->fn_tail = pnew_stu;
list->fn_count++;
return;
}
}
}
}
void add_ln_Node(LIST* list, NODE* pnew_stu) {
NODE* temp = list->ln_head;
if( list->ln_head == NULL ) {
pnew_stu->ln_next = list->ln_head;
pnew_stu->ln_pre = list->ln_head;
list->ln_head = pnew_stu;
list->ln_count = 1;
return;
}
else {
if ( (strcmp( pnew_stu->last_name, temp->last_name )) <= 0 ) { // Basa Ekleme Kosulu
pnew_stu->ln_next = temp;
pnew_stu->ln_pre = temp->ln_pre;
temp->ln_pre = pnew_stu;
list->ln_head = pnew_stu;
list->ln_count++;
return;
}
else {
while ( temp->ln_next != NULL ) { // Ortaya Ekleme Kosulu
if ( (strcmp( pnew_stu->last_name, temp->last_name ) >= 0 ) && (strcmp( pnew_stu->last_name, temp->ln_next->last_name) < 0)) {
pnew_stu->ln_next = temp->ln_next;
pnew_stu->ln_pre = temp;
temp->ln_next->ln_pre = pnew_stu;
temp->ln_next = pnew_stu;
list->ln_count++;
return;
}
temp = temp->ln_next;
}
if ( temp->ln_next == NULL ) { // Sona Ekleme Kosulu
temp->ln_next = pnew_stu;
pnew_stu->ln_pre = temp;
pnew_stu->ln_next = NULL;
list->ln_tail = pnew_stu;
list->ln_count++;
return;
}
}
}
}
我的删除功能:
void del_fn_name(LIST* list, char* str_key) {
NODE* temp;
int num,counter=1,flag;
temp = list->fn_head;
if( list->fn_head == NULL ) {
printf("The list is EMPTY!!!\n");
return;
}
flag = search_fn(list,str_key);
if ( flag ) {
printf("Enter the number of student you want to delete : ");
scanf("%d", &num);
if( strcmp( list->fn_head->first_name, str_key ) == 0 ) { // Bastan Silme Kosulu
if( num == counter ) {
list->fn_head->fn_next->fn_pre = list->fn_head;
list->fn_head = list->fn_head->fn_next;
free(list->fn_head);
printf("%s is deleted and the new header is %s\n", str_key, list->fn_head->first_name );
return;
}
counter++;
}
temp = temp->fn_next;
while ( temp->fn_next != NULL ) {
if( strcmp( temp->first_name, str_key ) == 0 ) {
if( num == counter ) {
temp->fn_pre->fn_next = temp->fn_next;
temp->fn_next->fn_pre = temp->fn_pre;
free(temp);
printf("%s deleted at between %s and %s\n", str_key, temp->fn_pre->first_name, temp->fn_next->first_name);
return;
}
counter++;
}
temp = temp->fn_next;
}
if( temp->fn_next == NULL ) { // Sondan Silme Kosulu
if( strcmp(temp->first_name, str_key) == 0 ) {
if( num == counter ) {
list->fn_tail = temp->fn_pre;
temp->fn_pre->fn_next = NULL;
free(temp);
printf("%s deleted at the end and new tail is %s \n", str_key, list->fn_tail->first_name );
return;
}
}
}
}
void del_ln_name(LIST* list, char* str_key) {
NODE* temp;
int num,counter=1,flag;
temp = list->ln_head;
if( list->ln_head == NULL ) {
printf("The list is EMPTY!!!\n");
return;
}
flag = search_ln(list,str_key);
if ( flag ) {
printf("Enter the number of student you want to delete : ");
scanf("%d", &num);
if( strcmp( list->ln_head->last_name, str_key ) == 0 ) { // Bastan Silme Kosulu
if( num == counter ) {
temp->ln_next->ln_pre = list->ln_head;
list->ln_head = temp->ln_next;
free(temp);
printf("%s is deleted and the new header is %s\n", str_key, list->ln_head->last_name );
return;
}
counter++;
}
temp = temp->ln_next;
while ( temp->ln_next != NULL ) {
if( strcmp( temp->last_name, str_key ) == 0 ) {
if( num == counter ) {
temp->ln_pre->ln_next = temp->ln_next;
temp->ln_next->ln_pre = temp->ln_pre;
free(temp);
printf("%s deleted at between %s and %s\n", str_key, temp->ln_pre->last_name, temp->ln_next->last_name);
return;
}
counter++;
}
temp = temp->ln_next;
}
if( temp->ln_next == NULL ) { // Sondan Silme Kosulu
printf("The last item %s second last item %s\n", temp->first_name, list->fn_tail->fn_pre->first_name);*/
if( strcmp(temp->last_name, str_key) == 0 ) {
if( num == counter ) {
list->ln_tail = temp->ln_pre;
temp->ln_pre->ln_next = NULL;
free(temp);
printf("%s deleted at the end and new tail is %s \n", str_key, list->ln_tail->last_name );
return;
}
}
}
}
整数flag,counter用于删除重复的学生.例如,如果有三个重复项,它会询问我要删除的学生人数.因此,如果我输入数字2,则删除第二个副本.
print(search(type ="cliente",codice = random.randrange(1000)))print(find(type ="cliente",codice = random.randrange(1000)))import sys sys.exit(1)
你的代码看起来有点复杂,但是这个想法是正确的.我没有看到插入方法中的任何错误,但很难遵循所有这种copy'n粘贴程序.您可以同时让每个学生在几个不同的列表中,但我建议使用不同的方法来避免所有这些重复,这使得很容易引入错误.
数据结构
你可以抽象出链接和列表的想法:
typedef struct TList
{
struct TLink *first, *last;
} List;
typedef struct TLink
{
struct TStudent *student;
struct TLink *prev, *next;
} Link;
该List结构是任何你所需要的三个列表(姓,名,出生日期)和Link任何的联系.见下图...
利用这种方法,用于插入/移除在列表中的链接的代码与所有链接类型(共享first_name,last_name,age).支付的价格是每个链接的额外指针,link->student->first_name而不是需要编写link->first_name.
链接插入/删除
添加链接到列表是类似的
// Adds a new link before the link `before` or as last link
// if `before` is NULL
void addLink(List *list, Link *newlink, Link *before)
{
newlink->next = before;
newlink->prev = before ? before->prev : list->last;
if (newlink->next) newlink->next->prev = newlink;
else list->last = newlink;
if (newlink->prev) newlink->prev->next = newlink;
else list->first = newlink;
}
并从列表中删除链接是类似的
void removeLink(List *lists, Link *link)
{
if (link->next) link->next->prev = link->prev;
else list->last = link->prev;
if (link->prev) link->prev->next = link->next;
else list->first = link->next;
}
这两个函数可用于管理所有三种类型(first_name,last_name和age)的列表/链接,而不需要任何代码重复.
插入Student对象
使用这种方法,学生对象可以拥有所有数据和许多链接对象
typedef struct TStudent
{
char first_name[NAMESIZE];
char last_name[NAMESIZE};
int age;
Link first_name_link, last_name_link, age_link;
} Student;
例如,为了first_name列出代码而插入学生
Student *newstudent = ...
...
Link *before = first_name_list.first;
while (before != NULL &&
strcmp(newstudent->first_name,
before->student->first_name) > 0)
{
before = before->next;
}
addLink(&first_name_list,
&newstudent->first_name_link,
before);
请注意,这个简单的循环正确处理代码中的所有情况,而不是使用类似语句的copy'n粘贴(这是第一个插入的学生,最后一个,中间的一个).
这里的想法是将before节点设置为列表中的第一个节点,并且如果必须在之后插入新节点,则将节点移动到下一个学生.
当然,在其他两个列表(last_name_list和age_list)中找到正确的插入点需要相同类型的循环.通过使用函数指针也可以考虑插入点搜索.
删除Student对象
要删除Student当然必须从所有列表中删除学生数据,换句话说,必须删除所有三个链接.然而,这仅仅意味着调用三次removeLink函数:
removeLink(&first_name_list, &student->first_name_link);
removeLink(&last_name_list, &student->last_name_link);
removeLink(&age_list, &student->age_link);
free(student);
| 归档时间： |
|
| 查看次数： |
7789 次 |
| 最近记录： |