第一题 利用环形列表 31 void kill_one(int m, int i) 32 { 33 link head = get_head(); 34 link node = head->next; 35 int len = 0; 36 while(node != head){ 37 if(i==m){ 38 printf("=========ko------------------=%d\n", node->item); 39 delete(node); 40 i=0; 41 } 42 i++; 43 node = node->next; 44 } 45 list_node(); 46 head = get_head(); 47 for(node=head; node->next != head; node=node->next){ 48 len++; 49 } 50 if(len>=m){ 51 printf("------------------\n"); 52 kill_one(m, i); 53 }else{ 54 printf("head->next->item=%d\n", head->next->item); 55 } 56 }
看到这里我受益非浅但在看【链表】这章的时候我看了好几遍都没有看懂,在他人的指导下明白了,我感觉以开始理论性知识太少。我个人的建议
第一题答案: #include <stdio.h> #include <stdlib.h> #include <time.h> #include <unistd.h> #include <string.h> //item structure typedef struct person_tmp{ int num; struct person_tmp *prev; struct person_tmp *next; } person_t; int delete(person_t * *p); //delete current item and *p point the previous one; int dump_trash(int trash[], int n); //print these deleted items; int main(void) { const int TOTAL = 108; person_t circle[TOTAL+1]; //initialize circle; person_t *head = &circle[0]; //the pointer to head node; person_t *curp=NULL; //current item pointer; int n = TOTAL; int trash[TOTAL/3+1], top=-1; //to holds deleted items; int i; for(i=0; i<TOTAL+1; i++){ circle[i].num = i; circle[i].prev = &circle[i-1]; circle[i].next = &circle[i+1]; } circle[0].prev = &circle[TOTAL]; circle[TOTAL].next = &circle[0]; //initialized linked list; curp=head, i=1, top=-1; do{ curp=curp->next, i++; if(curp == head){ curp = curp->next; dump_trash(trash, top+1), top=-1; } if(i == 3){ trash[++top] = curp->num; delete(&curp), //delete current item, p point the i = 0, //previous item; so i = 0; n--; } }while(n>2); dump_trash(trash, top+1), top=-1; return 0; } int delete(person_t * *p) { (*p)->prev->next = (*p)->next; (*p)->next->prev = (*p)->prev; *p = (*p)->prev; // *p point the previous item; return 0; } int dump_trash(int trash[], int n) { int i; printf("count:%d\n", n); for(i=0; i<n; i++){ printf("%d ", trash[i]); } printf("\n"); return 0; }
第二题答案: 需要注意的是,数据结构一定要采用双向循环链表,否则操作起来很困难; 上半部分: #include <stdio.h> #include <stdlib.h> #include <time.h> #include <unistd.h> #include <string.h> #define BUFF_MAX 128 //item structure typedef struct stamp_tmp{ int time[7]; struct stamp_tmp *prev; struct stamp_tmp *next; } stamp_t; stamp_t *preproc(stamp_t *stamp, char *buff); //convert strings stored in buff to stamp_t and store in stamp. stamp_t *insert_sort(stamp_t *head, int (*compare)(stamp_t *stamp1, stamp_t *stamp2)); //insert sort int compare(stamp_t *stamp1, stamp_t *stamp2); //compare two stamps; stamp_t *insert(stamp_t *before, stamp_t *curp); //insert a stamp_t item into linked list; int destroy_list(stamp_t *head); //free the memory of linked list; int main(int argc, char *argv[]) { char buff[BUFF_MAX] = {'\0'}; stamp_t *head, *curp, *tmpp; FILE *fpsrc, *fpdes; int i; if(argc != 3){ fprintf(stderr,"arguments error!\n"); exit(2); } if((fpsrc=fopen(argv[1], "r"))==NULL){ perror(argv[1]); exit(1); } if((fpdes=fopen(argv[2], "a+"))==NULL){ perror(argv[1]); exit(1); } head = malloc(sizeof(stamp_t)); head->prev = head, head->next = head; curp=head; while(fgets(buff, BUFF_MAX, fpsrc)!=NULL){ tmpp = malloc(sizeof(stamp_t)); preproc(tmpp, buff); insert(curp, tmpp), curp=tmpp; } insert_sort(head, compare); //sort the linked list; for(curp=head->next, i=1; curp!=head; curp=curp->next, i++){ snprintf(buff, BUFF_MAX, "%d %d-%d-%d %02d:%02d:%02d\n", i, curp->time[1], curp->time[2], curp->time[3], curp->time[4], curp->time[5], curp->time[6]); if(fputs(buff, fpdes) == EOF){ perror(argv[2]); exit(1); } } destroy_list(head), head=NULL;//free the memory of list; return 0; }
下半部分: stamp_t *preproc(stamp_t *stamp, char *buff) { int i, j; for(i=0, j=0; i<7; i++){ for(; !(buff[j]>='0' && buff[j]<='9'); j++); // jump non digit; stamp->time[i] = atoi(&buff[j]); for(; buff[j]>='0' && buff[j]<='9'; j++); // jump digit; } return stamp; } int compare(stamp_t *stamp1, stamp_t *stamp2) { int i, tmp; for(i=4; i<7; i++){ tmp = stamp1->time[i] - stamp2->time[i]; if(tmp!=0) return tmp; } for(i=1; i<4; i++){ tmp = stamp1->time[i] - stamp2->time[i]; if(tmp!=0) return tmp; } return 0; } stamp_t *insert(stamp_t *before, stamp_t *curp) { curp->next = before->next, curp->next->prev = curp; curp->prev = before, curp->prev->next = curp; return curp; } stamp_t *insert_sort(stamp_t *head, int (*compare)(stamp_t *stamp1, stamp_t *stamp2)) { stamp_t *p1, *p2, *tmpp; if(head->next == head || head->next->next == head) return head; for(p1=head->next->next; p1!=head; p1 = tmpp){ tmpp = p1->next; for(p2=p1->prev; //find where *p1 should be; p2!=head && compare(p2, p1)>0; p2=p2->prev); p1->prev->next = p1->next, p1->next->prev = p1->prev;//disconnect *p1; insert(p2, p1); // connect *p1 behind p2; } return head; } int destroy_list(stamp_t *head) { stamp_t *curp = NULL; //reach to the end; for(curp = head->prev->prev; curp != head; curp=curp->prev) free(curp->next); free(curp); return 0; }
第一题答案: #include <stdlib.h> static link head = NULL; static link tail = NULL; static unsigned long count=0; link make_node(unsigned long item) { link p = malloc(sizeof *p); p->item = item; p->next = NULL; p->prev = NULL; return p; } void free_node(link p) { if(p) free(p); } void insert(link p) { if(!p) return; if(!head) { head=p; tail=p; p->next=NULL; p->prev=NULL; count++; return; } tail->next=p; head->prev=p; p->prev=tail; p->next=head; tail=p; count++; } void delete(link p) { if(!p) return; if(head==tail) { head=tail=NULL; return; } p->prev->next=p->next; p->next->prev=p->prev; if(p==tail) { tail=p->prev; } else if(p==head) { head=p->next; } count--; } unsigned long get_count(void) { return count; } link get_head(void) { return head; } void traverse(void (*visit)(link)) { link p; p=head; visit(p); do { p=p->next; visit(p); }while(p!=tail); } #define N 100 #define M 3 void print_item_removed(link p) { printf("%u has been removed!\n",p->item); } void print_item_exist(link p) { printf("%u exist!\n",p->item); } int main() { link p,phead; int i; for(i=1;i<=N;i++) { p=make_node((unsigned long)i); insert(p); } i=1; p=phead=get_head(); #if 1 while(get_count()>=M) { if(i%M==0) { delete(p); print_item_removed(p); } p=p->next; i++; } #endif printf("the left cell is :\n"); printf("the number of the left cells is %d\n",get_count()); traverse(print_item_exist); return 0; }
如果您有建设性意见,哪怕只是纠正一个错别字,也请不吝赐教,您留下的姓名和email将会出现在本书前言的致谢中。再次感谢您的宝贵意见!