这天要面试，提前把链表操作重新写了一遍。备份一下，以备不时之需。
希望有人能看到这篇代码，并指正。
// File Name : list.h
#include "stdafx.h"
#include "stdio.h"
#include <stdlib.h>
#include "string.h" //creat list
//creat node
//insert
//del
//find
//sort
typedef int data_t ;
typedef struct NODE{
data_t data;
NODE* next;
}NODE ,*NODEPTR; typedef struct LIST{
NODE* head;//init==0
NODE* tail;//init==0
int num ; //min==0
}LIST; //create
extern NODE *create_node(data_t data);
extern LIST *creat_list();
extern bool is_null(LIST* list);
//find
extern NODE* find_node(LIST* list ,data_t data);
extern NODE* inline find_node_by_index(LIST* list , int index);//index : from 1 to list->num //del
extern int del_node_data(LIST* list,data_t data);
extern data_t del_node_head(LIST* list );
extern data_t del_node_index(LIST* list,int index);//index : from 1 to list->num
extern data_t del_node_tail(LIST* list ); //insert
extern int insert_data_F(LIST* list, data_t data);
extern void insert_node_F(LIST* list, NODE* node);
extern int insert_data_T(LIST* list, data_t data);
extern void insert_node_T(LIST* list, NODE* node );
extern int insert_data_index(LIST* list , data_t data,int index);//index : from 1 to list->num
extern int insert_node_index(LIST* list , NODE* node,int index);//index : from 1 to list->num extern int insert_data_ordered(LIST* list , data_t data );//assume the list is ordered (low to high )
//sort
extern int sort(LIST* list);
extern int swap(LIST* list, int indexf,int indexn);//index : from 1 to list->num
extern int inline swap_node(NODE* before ,NODE* next);
/****************************************************************************** Copyright (C), 2001-2011, DCN Co., Ltd. ******************************************************************************
File Name : list.c
Version : Initial Draft
Author : ocj
Created : 2014/8/8
Last Modified :
Description : singlelist
Function List :
create_node
creat_list
del_node_data
del_node_head
del_node_index
del_node_tail
find_node
find_node_by_index
insert_data_F
insert_data_index
insert_data_ordered
insert_data_T
insert_node_F
insert_node_index
insert_node_T
is_null
sort
swap
swap_node
History :
1.Date : 2014/8/8
Author : ocj
Modification: Created file ******************************************************************************/
#include "list.h"
//if success :ret!=0
LIST *creat_list()
{
LIST* list = (LIST*)malloc(sizeof(LIST));
list->head = ;
list->tail = ;
list->num = ;
return list;
}
//if success :ret!=0
NODE *create_node(data_t data)
{
NODE* node = (NODE*)malloc(sizeof(NODE));
node->dext = ;
node.data = data;
return node;
} //return 1: is null
//return 0: not null
bool is_null(LIST* list)
{
//return (list->num==0); //method 1
return (list->head->next == ) ;//method 2
} //ret==0:fail
int insert_node_F(LIST* list, NODE* node)
{
if(list== || node ==){
return ;
}
if(list->head==){
list->tail = node;
}
list->head = node ;
node->next = list->head;
//if list is null ,node->next == list->head==0
//if list is not null ,node->next == list->head!=0
list->num++;
} //return 1 : ok
//return 0 : fail
int insert_data_F(LIST* list, data_t data)
{
NODE* node = create_node(data);
if(node){
return ;
}
insert_node_F(list , node);
return ;
} void insert_node_T(LIST* list, NODE* node )
{
if(list->head==){
node->next = ;
list->head = list->tail = node;
} list->tail = node ;
node->next = ;
list->num++;
} //return 1 : ok
//return 0 : fail
int insert_data_T(LIST* list, data_t data)
{
NODE* node = create_node(data);
if(node){
return ;
}
insert_node_T(list , node);
return ;
} //ret=0: fail
int insert_node_index(LIST* list , NODE* node,int index)
{
if(index>listnum+) {
return ;
} if(index==){
insert_node_F(list ,node);
}else if(index ==list->num+){
insert_node_T(list ,node);
}else{
NODE* before = list->head;
while(index>){
index--;
before = before->next;
}
node->next = before->next ;
before->next = node ;
list->num++;
}
return ;
}
//ret=0: fail
int insert_data_index(LIST* list , data_t data,int index)
{
NODE* node = create_node(data) ;
if(node==null){
return ;
}
return insert_node_index(list , node,index );
} //assume the order is low to high
//ret==0: fail
int insert_data_ordered(LIST* list , data_t data )
{
NODE* node = create_node(data);
if(node==){
return ;
}
if(list->head == ){
list->head = list->tail = node;
return ;
} if(node->data < head->data){
insert_data_F(list ,node);
}else {
list->num++;
NODE *before = head;
NODE* nodet = head->next ;
while(node->data > nodet->data && nodet->next!=){
//until( node->data < nodet->data || tail )
nodet = nodet->next ;
before = before->next;
}
if(nodet->next==){
nodet->next = node ;
}else{
node->next = nodet ;
before->next = node ;
}
}
return ;
} //not find: return 0
//success find and del :return 1
int del_node_data(LIST* list,data_t data) //find and del first_found
{
if(list->num ==){
return ;
} NODE* before = list->head ;
NODE* nodet = list->head ;
if(nodet->data == data){ //head->data == data
list->head = list->head->next ;
free(nodet);
list->num--;
return ;
} nodet = nodet->next;
while(nodet->data!=data && nodet->next!= ){
nodet = nodet->next;
}
if(nodet->data == data ){
before->next = nodet->next ;
free(nodet);
list->num--;
}else{//not found
return ;
}
return ;
} data_t del_node_index(LIST* list,int index)
{
if(is_null(list) || index > list->num){
exit(-);
}
NODE* before = list->head ;
NODE* del = list->head ;
data_t data ;
if(list->num == ) { //head
list->num--;
list->head = list->tail = ;
data = del->data;
free(del);
return data;
} int first = ;
for( ;index>;index--){//offset --- index
if(!first){
before = before->next ;
}
first = ;
del = del->next;
} before->next = del->next ;
data = del->data;
if(del==list->tail){
list->tail = before ;
}
free(del);
list->num--;
return data; }
data_t del_node_head(LIST* list )
{
if(is_null(list)){
exit(-) ;
}
data_t data ;
NODE* del = list->head ;
list->head = list->head->next ;
free(del);
list->num--;
return data;
}
data_t del_node_tail(LIST* list )
{
if(is_null(list)){
exit(-) ;
}
NODE *before = list->head ;
data_t data = list->tail->data; if(list->num ==){
list->head = list->tail = ;
list->num--;
free(before);
return data ;
} while(before->next!= && before->next->next != ) {
before = before->next ;
} list->tail = before;
list->num--;
free(before->next);
return data ;
} //return 0: fail to find
//return node* : node first_found
NODE* find_node(LIST* list ,data_t data)
{
if(is_null(list)){
return ;
} NODE* nodet = list->head;
do{
if(nodet->data == data)
return nodet;
}while(nodet->next!=); return ;
} //head_index == 1;
//return 0: fail to find
//return node* : node first_found
NODE* inline find_node_by_index(LIST* list , int index)
{
if(list== || list->num == || index > list->num){
return ;
}
NODE* find = list->head;
while(--index){
find =find->next;
}
return find ;
} int swap(LIST* list, int indexf,int indexn)
{
NODE* nodef = find_node( list , indexf ) ;
NODE* noden = find_node( list , indexn ) ;
data_t swp = nodef->data;
nodef->data = noden->data;
noden->data = swp->data;
} //ret==0 : fail
int inline swap_node(NODE* before ,NODE* next)
{
if(before == ||next == ){
return ;
}
before->data ^=next->data ;
next->data ^=before->data ;
before->data ^=next->data ;
} //asume from little to big
int sort(LIST* list)
{
int times;
int index;
NODE* before = list->head;
NODE* next = ;
if(list==){
return ;
}
if(list->num==){
return ;
}
for(times=;times<list->num ;times++){
for(index=;index<=size-times;index++){
before = find_node_by_index(list ,index);
next = before->next;
if(next->data<before->data){
//before->data = before->data^ next->data ;
//nexty->data = before->data^ next->data ;
//before->data = before->data^ next->data ;
swap_node(before , next);
}
}
return ;
}